The Expressive Capacity of State Space Models: A Formal Language Perspective
Authors: Yash Sarrof
Yana Veitsman
Michael Hahn
Venue: NeurIPS 2024 poster (2024)
Keywords: state-space models
formal languages
expressivity
theory
Primary area: deep_learning_architectures
TL;DR: We theoretically investigate the expressive capacity of modern state-space models.

Abstract: Recently, recurrent models based on linear state space models  (SSMs) have shown promising performance in language modeling (LM), competititve with transformers. However, there is little understanding of the in-principle abilities of such models, which could provide useful guidance to the search for better LM architectures. We present a comprehensive theoretical study of the capacity of such SSMs as it compares to that of transformers and traditional RNNs. We find that SSMs and transformers have overlapping but distinct strengths. In star-free state tracking, SSMs implement straightforward and exact solutions to problems that transformers struggle to represent exactly. They can also model bounded hierarchical structure with optimal memory even without simulating a stack. On the other hand, we identify a design choice in current SSMs that limits their expressive power. We discuss implications for SSM and LM research, and verify results empirically on a recent SSM, Mamba.

The Expressive Capacity of State Space Models: A Formal Language Perspective
Yash Sarrof, Yana Veitsman, Michael Hahn
Saarland Informatics Campus
Saarland University, Germany
(ysarrof, yanav, mhahn) @lst. -wi--siaiaaaaaaa srearland.co
Abstract
Recently, recurrent models based linear state space models (SSMs) have shown promising performance in language modeling (LM), competititve with transform- ers. However, there is little understanding of the in-rrinciple abilities of such models, which could provide useful guidance to the search for better LM architec- tures. We present comprehensive theoretical study of the capacity such SSMs as it compares to that of transformers and traditional RNNs. We find that SSMs and transformers have overlapping but distinct strengths. star-free state track- ing, SSMs implement length-genne generalizing solutions to problems that transformers struggle to represent exactly. They can also model bounded hierarchical structure with optimal memory even without simulating stack. On the other hand, we identify a design choice current SSMs that limits their expressive power. We discuss implications for SSM and LM research, and verify results empirically on a recent SSM, Mamba.
Introduction
Transformers Vaswani al. 2017 power most large language models (LLMs) today, as they offer the advantage of parallelized training by avoiding recurrence, compared to the previously dominant
recurrent achitectures [RNNs Elman 1990 Hochreiter and Schmidhuberi 1997] However, building
on long history of continuous dynamical models [c.g. Kalman 1960 1963 and work on faster
RNNs [Bradbury et al.] 2016 Lei et al. 2018). recent line of work has developed state space
models (SSMs) rivaling the performance of transformers [c.g. Gu et al. 2021 Gu and Dao, 2023
Sun al. 2023 De et al. 2024 Yang et al., 2024 Qin et al. 20024a]. These SSMs are recurrent models, formulated in terms of iterative state updates, while still allowing efficient parallelization.
The impressive empirical performance of such SSMs raises the question of whether they might have capabilities that the transformer architecture might lack in principle. Simultaneously. to understand whether SSMs may plausibly overtake the dominant role of transformers, it an important question whether SSMs may lack abilities present in transformers. A better understanding of these questions may also point the way to future architectures that unite the strengths of both architectures.
One common approach to understanding the capabilities of computational architectures is through their expressive capacity in simulating automata and modeling language classes; indeed, sizeable literature has studied transformers Pérez et al.
Pérez
2019
Hahn 2020 Bhhttamishra et al. 2020
Yao al. 202 Liu al.] 2023b a Deletang et al.
2022 Strobl et al. 2024|Chiang
al. 2023
Sanford et al. 2024 Peng et al. 2024] and RNNs [e.g.
Siegelman and Sontag 1995 Horne and
Hush
1993
Indyk 1995 Weiss al. 2018 Hewitt
2020 through this lens. As the difficulty
!ooee available at: http://ghhhhheooommmooooobbbssee
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

of many computational problems is well-understood in terms of such language classes, results about expressive capacity directly yield results about the ability to model specific computational problems.
While a substantial number of results have been obtained for transformers and traditional RNNs, understanding remains largely open for SSMs. In initial step, |Merill et al. (024] showed that all problems computable by SSMs are contained in TC a circuit complexity class that is known to
also cover transformers [Merrill and Sabharwal 2023 Strobl 2023]. Under standard conjectures, this suggests that certain types of state tracking are hard for both models. Pelassi et al.) (2024) and
Bhattamishra et al. [2024] provided evidence of differences between these architectures, showing that transformers outperform SSMs on copying retrieving from long strings- tasks well within TC Zubić et al. (2024) showed that multi-layer SSMs are constrained by their logarithmic space computational capacity, limiting their ability at algorithmic tasks such as multi-digh multiplication.
However, more fine-grained understanding of the power of SSMs, and how they compare RNNs and transformers, remains an open question. Our contribution in this paper is to provide rigorous understanding of SSMs' abilities in different classes of languages. We show that transformers and SSMs cover overlapping but distinct fragments of TC For instance, SSMs can model bounded hierarchical structure ways similar transformers and traditional RNNs, even without embedding a stack-like structure (Theorem 6 For regular languages involving modular counting, such as the PARITY function (Theorem 2). we identify a design choice that makes extant SSMs struggle in ways similar to transformers. In other cases, we show that SSMs resolve a failure case of transformers: they effortlessly model Flip Flop state tracking (Theorem [T] We discuss take-aways for SSM and I.M research in Section 5 among others, our results suggest future LM architectures might need to combine both attention and state spaces.
2 Background
2.1 State Space Models
SSM Layers
We define a single layer of state space model as map, input length T, R
Txd
7xd
(x+)r=1.... + (2...
given by the recurrence
h; Ax; - B(x)
(I)
where o denotes elementwise product, and, for each x E Rdd
ho ERd
B(x;) E Rd (increment)
A(x)) ER (gate)
:: R RR (transform)
We allow A, to be arbitrary smooth maps. The map xh,,,;; includes a cascade of channel-mixing transformations and normalization, which we abstract as follows:
(b),,x Mix; (Norm MMxx (hx,)))))))
where M-xy(-) can contain linear (Swi)GLU components [e.g. Qin al. 2024a Gu and Dao
2023
We will take Norm to implement RMSNorm Zhang and Sennrich 2019: LayerNorm Ba
ct al. 2016 can be covered by absorbing centering into Mix2.
A Full SSM Real-world SSMs typically stack several layers of the form 2 Where needed, we use superscripts indicate the layers in an SSM: in"), .I.,....!!! (i(), where is the number of layers. We consider input words w = Wi.../w| over a discrete alphabet Σ, and assume an encoding in terms
of token embeddings e(o) E Rd. for a E. We will also write ea for e(a). These feed into the lowest layer as x;") = e(w)). The outputs of each layer feed into the next layer, as ,; (1+1) = (1) The transformations in 1 are specific to each layer: simple, we will only show the superseripts where necessary for disambiguation. The activations
and similarly for B, 4. To keep notation
4 at the highest layer are read out by some neural network p into vectors 4: Ropes describing classification or next-token predictions. We again take p to be an arbitrary function; importantly, all our constructions will allow p to operate correctly even at finite precision.

---

Implementation Choices In Mamba. directly maps onto Eqs. (2a) and (2b) in Gu and Dao (2023). The notation Gf and Dao 2023 use a matrix multiplication Ah, instead of elementwise multiplication A ) o
in I but importantly Mamba's A is diagonal, so we can take A Axx); ) Ag- Some SSMs assume nondiagonal A(x),, ). but typically this matrix diagonalizable [e.g. Gu et al,, 2021 Sun et al., 2023). so that the SSM is still equivalent to one of the form (T). We discuss how other SSMs instantiate (T) in Appendix A Some models assume complex-vaie cealuee-aluued activations (Appendix A our results largely do not depend on this distinction, but take it into account where needed (Theorem 13}. Some SSMs [e.g. Gu and Dao 2023] use different numbers of channels in 3; and h using state expansion; as this does not affect expressive capacity, will simply assume constant dimensionality d. Local convolutions [e.g. Fu et al. 2023 can be simulated with an SSM layer and do not increase expressive capacity (Remark
We will find that two design choices have nontrivial impact on expressive capacity: The first one time invariance: we call an SSM TIME-INVARIANT if A(x) does not depend on x;- Some SSMs, such as $4 [Gu et al.] [02T] and Retnet (Sun et al.
2023 are time-invariant; Mamba (Gu and Dao, 2023]. Griffin De et al. 2024). GLA Yang et al. 2024), HGRN [Qin al.] 2024b|a]. QRNN/SRU Bradbury et al. [0016). Lei et al. (2018) are not (Appendix (A). The second one is the sign of the
entries of Axx): Across all non-time-invarian SSMs surveyed, we find that the gate is always non- negative (Appendix Ap: (xx) 2 0 (NONNEGATIVE) due to exponential or sigmoid parameterizations
of the gate this choice turns out to limit expressive capacity (Theorem 2
Role of Parameterization While the abstract form 1 is common across the SSM literature, differences in parameterization may have substantial effect on efficiency and training stability. In particular, the parameterizaation of (xx, has been the subject of substantial research [c.g. Gu al., 2020 [021] Yu et al., 2023, Wang and Li. 2023]. However, studying expressiveness allows us to abstract away from these differences to a remarkable degree: We will allow A. p be arbitrary functions with the given input-output properties. Our negative results are based on abstract prop- erties of the setup 2 which fundamentally bottlenecks SSMs through elementwise linear state updates. For our positive results, will use empirical learnability experiments to verify that learnable solutions instantiating them (though not necessarily implementing the same constructions as used in the proofs) do exist in recent SSM [Mamba, Gu and Dao 2023
We contrast SSMs with traditional RNNs such as simple RNNs LSTMs: for these, the recurrence in Eq. is replaced by h, (h 1.4)) where v could be linear, an MLP [Elann 1990], or more complex gated function (Hochreiter and Schmidhuber 1997].
Finite Precision Assumption While Eq. assumes arbitrary real-valued activations, real-world implementations can only represent numbers with bounded precision. Formally, we adopt the finite precision notion used by Weiss et al. [2018) in a study of the expressive power of traditional RNNs: We allow an unbounded number of integer bits, but only fractional bits, independent of the length of the input. See Appendix E for discussion.
2.2 Modeling Formal languages
We study three foundational types of data structures needed for modeling formal languages (Hopcroft et al., 200T]: finite state automata (Theorem [ counters (Theorem [5) and stacks (Theorem 6). These data structures can be understood in two equivalent forms: One is to track state sequence over an input, where each input symbol engenders a specific transformation on the state. The other one, more commonly considered in research on expressive capacity, considers for- mal languages- sets of finite strings that are defined by the property that an automaton reaches one of pre-specified set of "accepting" states after traversing the word. We focus on the latter, enabling easy comparison with existing results on transformers and RNNs.
A fmite-state-automatoo (see Definition 7 represents general state tracking problem over finite state space, without imposing further structure on the state space: The automaton keeps track of a single state from a finite state space; when reading string from left to right, each symbol engenders a specific transformation of the state. At each position, the current state determines which symbols can come next; membership in formal language is determined by the state reached after reading the full string. cniite-state-uttomee are equivalent expressivity to regular expressions, and define the regular languages [Kleene 1951].
3

---

Dyckgs
Stock
Figure 1: Three key formal languages: prefixes with the sets of possible next characters: Flip Flop (Theorem[] D PARITY (Theorem bounded-depth Dyck (Theorem In Flip Flop, after z (read) instruction, the bit must match what came after the last w (write) instruction (here, 0). For PARITY, EOS can only follow when the number of ones in the prefix is even. For bounded-depth Dyck, a closing bracket only appear if it matches the last unclosed opening bracket (here, ")" matches "(")). Opening brackets can appear as long as the maximum depth (here, 5) hasn't 't been reached.
Allowing an automaton to keep track of one or more counters (Fischer et al. 1968b integers that are incremented or decremented at each symbol read-turns the state space infinite, but in highly structured manner. SSMs can model this datastructure (Theorem (). as can RNNs and transformers [Weiss et al., 2018 Bhattamishra et al. 2020]. Stacks, a first-in-first-wn datastructure, enable automata keep track of hierarchical structure, foundational to natural language (Chomsky) 1957]. We show that SSMs can implement shortcut solutions to bounded hierarchical structure even without implementing stack (Theorem 66 these are likely to be most useful to natural language given the boundedness of human memory Miller 1963
Karlsson 2007
2.3 Formal Language Prediction and Recognition
We fix finite alphabet Σ. Its elements are called characters or symbols. The set of all finite strings over Σ is denoted Σx; such strings are often referred to as words. The length of is denoted |w| A formal language L is a subset of E.. Techically, we assume that the alphabet includes BOS and EOS symbols, which occurs at the beginming and end of each element of L and nowhere else.
We next need to define what it means for an SSM to model formal language. The notion of recognition, where the task is to classify a full string as belonging to the language or not. Formally, for an SSM with dl pred 1, we we say that it recognizes language if the output p(z()) equals when the SSM is run on w E E"-1 if w E L and 0 else.
However, such classification task is arguably not always matched to dominant cases in pre- dictive sequence modeling, where the task is to predict the next token at each step. Thus, we also cast formal languages into language modeling and sequence prediction framework. We adopt the task of Bhattamishra et al. 2020), where the model is asked to output at each step in a sequence the set of possible next symbols. Let Prefix
{w Σ" w." O o 0} the set of valid prefixes of L. We then say that a model predictively models a language if (Figure []] given a valid prefix Prefix(L), outputs the finite set
{o E W: 00
(3)
We think of each such set as an atomic label; the of possible labels the power set of the finite alphabet (here, dpreed 2).) Importantly, in both recognition and predictive modeling, we test the SSMs' ability across arbitrary input lengths, i.e. the choice of input length does not affect the inherent capability to recognize or predictively model the language. Predictive modeling can be easily converted into recognition by checking whether any symbol in the sequence is not in the predictive set at the preceding position; this can done by adding SSM layer. Conversely, if we can show that SSMs cannot recognize language, this proves they also cannot perform predictive modeling for it, as they then cannot correctly predict where EOS can appear. To get the strongest results, we thus prove positive results for predictive modeling, and negative results for recognition.

---

Time Invariant
H
count up
H
A(O)=
mix/norm
B
count down
Non-Negative
(a) SSM Equation
(b) SSMs Parity
Unbounded Counting
Figure 2: (a) Visualizing the SSM equations 1 The hidden state H is updated by combination of its previous values, transformed by matrix A, and the input X, modulated by matrix B. The updated hidden state and input are then processed through Mix(.) layer, which can incorporate components like (Swi)GLU or Linear layers, with an optional R.MSNorm for normalization. (b) An intuitive construction for recognizing PARITY with SSMs is achieved by setting B = 0 and A = -1 when the input is 1, and A = otherwise. However, this construction violates both NONNEGATIVE and TIME-INVARIANT properties. We show that one of these properties is provably required to recognize PARITY at arbitrary lengths using an SSM (Theorem 2). (c) Modeling a"b": the matrix A adds the previous hidden state to the update, and depending on whether the input symbol requires counting up or down, matrix B is set to I or - thus making the SSM simulate a counter (Theorem 5
layer,
3 Theoretical Results
3.1 Length-Generalizing Representations for Flip-Flop State Tracking
Flip Flop languages [iu et al. 2023a] are a simple instance of state tracking defined in terms of write, read, and ignore instructions. Each write instruction comes with piece of information; whenever a read instruction is encountered, the information written by the last write instruction is recalled. Formally, LFF is the set of finite strings x over Σ = (I, 1, 0,0,1,, 1}, where A1, E {r, w, i}. X2. E {0. 1}. and where the bit following any r matches the bit following the last preceding occurrence of w. Liu al.) [2023b) show that the Flip Flop language. as an abstraction, is fundamental ingredient of many long-range reasoning settings. It can be represented with a small saaee-state-automatte
and LSTMs learn LPF well [Liu al., 2023a] Transformers principle represent it [Liu et al., 2023b]al a). though known constructions are not inherently length- generalizing, fact contirmed empirically; intuitively, this may happen because attention heads aggregate information in a commutative manner, and reliably attending to the last write instruction requires strong position dependence in the attention weights. SSMs, similar to traditional RNNs can easily represent Flip Flop at arbitrary input lengths and thus avoid a failure mode of self attention:
in
Theorem 1. There a two-layer SSM that predictively models LFp at all lengths, at finite precision.
In the construction (Fi the first layer records the last instruction token, achieved in ① by set- ting A(e(r)) = =(e(x))=AA((3))
0, and (ee(0) = =Aee(1)) 1, and setting B(e(O)) B(e =0. O. Additional dimensions forward the current token to n. In the output of the first layer 2 (1) when- ever the input is 0 or 1, the model now has access both to the current token w, and the preceding token w,-1. which must have been an instruction. Based on this information, the model can set the gate to overwrite the state n121 with the current input token when the preceding token w,
and pass along the state 112) unaltered otherwise. This, together with (1) is sufficient for always identifying the legal next symbols in LFF. The formal proof is in Appendix B.I
3.2 Difficulty of PARITY
PARITY, the language of bitstrings with an even number of ones, is recognized by a finite-state automaton with 2 states, and is straightforwardly encoded into a traditional RNN, even a linear one, with finite precision. It is in principle expressible for transformers [Chiang and Cholak 2022], but is empirically hard for transformers to learn (Bhattamishra et al.] |020 Deletang et al. 2022]. as it can provably only be represented in sharp minima [Hahn and Rofin 2024]. sufficiently general SSM could easily recognize it at d= by setting An- = 1, A(e)) sign of the single entry of h, indicates the parity (Figure 2 Such an SSM would need to be non- Lime-invarian and require negative or complex gate values; i.e., satisfy neither
A(e))) = 0, B = 0, so that the
5

---

TaE Layer
2nd Layer
THt Layer
2nd Layer
whhhl
Nowe
depth
close
0/1 B
Ar1
Bm-1
Farth
deyth
clsselopen
WAYi
Michorn
Locer ietructionn
Oormen Toiee
Mannim
Corredt
Yalue
Art
(a) SSM Flip Flop Construction
D51 hi Construction
Figure 3: (a) Construction for Flip-Flop (Theorem I The first layer stores instruction bits to the hidden state, while data bits are forwarded to the output. Hence, the output always contains both the latest instruction and the associated data bit. In the second layer, if the instruction bit is w, the corresponding data bit is written to the hidden state, else the old value persists. This allows the model to consistently output the correct data bit. (b) Construction for Dyck(K, h) (Theorem o The first layer tracks the depth by counting up for each opening bracket, and down for each closing bracket. The second layer builds on the Flip-Flop construction to find the last opening bracket at the current depth; the next symbol can be either the matching closing bracket or if the maximum depth has not been reached - an arbitrary opening bracket.
nor NONNEGATIVE. Thus, these design choices necessitated by optimization, limit the power of an SSM in emulating finite-state-automataa establishing an even stronger separation between existing SSM variants and traditional RNNs than the circuit complexity arguments in Merrill et al. 22024]
Theorem 2. No SSM satisfying NONNEGATIVE can recognize PARITY at arbitrary input lengths with finite precision. In particular, this applies to Mamba.
The proof is in Appendix B.2 it examines inputs of the form I and shows that the activations IN converge as N + co, and thus cannot reliably encode the parity of N. It should be noted that we require the layer-wise operations used in the SSM be either linear or based on the GLU or SwiGLU activation functions, as seen for instance in Mamba (Remark [1).. As we show in Theorem [3] the same result holds even for SSMs evading NONNEGATIVE when they are TIME-INVARIANS when the coefficients have rational angles in the complex planes. All extant SSMs we surveyed (Appendix, Section A) satisfy either NONNEGATIVE or TIME-INVARIANT. Hypothetical SSMs evading both NONNEGATIVE and TIME-INVARIANT would be strictly stronger and can represent not only PARITY, but all regular languages known to be in TC (Theorem 22
least
3.3 Exact characterization of Regular Languages modeled by SSMs
We combine Theorems 1 and 2 to derive an exact characterizations of the regular languages that modern -onttime-nvvarian SSMs such as Mamba can recognize or predictively model the two notions coincide here in the finite-precision setting. The key insight is that LFF and PARITY are fundamental building blocks of two classes of regular languages: star-free languages and their complement, non-star-free languages (Schüizenbergerr) 1965, McNaughton and Paperi 1971):
Definition 3. A regular language is star-free if it can be defined using regular expressions involving only the empty set. the empty string. individual symbols, concatenation, and Boolean combinations -avoiding the Kleene slur operation.
LFF is star-free: there is a way to define it without Kleene star. PARITY is not star-free; any regular expression for it must involve the Kleene star. Some languages that are intuitively defined with Kleene stars may still be star-free using only first-order quantifiers and the order relation [Schötzenberger 1965). Also, L is non-star- free if and only if recognizing it involves counting modulo some finite integer K (McNaughton and Papert 1971]; J; Modern non-time-inven invariinariant SSMs such as Mamba cannot perform modulo counting, but they can model all star-free languages:
A language is star-free if and only if it can be defined logically
Theorem 4. Let L be a regular language. The following are equivalent:
For example. (01)* is star free. It is the union of with the intersection of OΣ", E",, with the complements of E 5'000* and In 11...

---

1. There is an SSM satisfying NONNEGATIVE that predictively models L at all input lengths, at finite precision
2. L is star-free.
The proof in Appendix B.3 uses the Krohn-Rhodes theorem [Krohn and Rhodes] 1965] to reduce all star-free languages to flip flop-like state tracking. Importantly, there are well-known constructive criteria for deciding whether a given automaton defines a star-free frre language [Schützenberger 1965]; hence, we have decidable criterion for the finite-state tracking problems that such SSMs satisfying NONNEGATIVE can solve.
This is much simpler than the situation for transformers, where an exact characterization of their power within the regular languages is complicated: [Angluin et al. (2023) show that a certain for- mal abstraction of transformers (masked unique hard attention) also recognizes exactly the star-free languages, but constructions of realistic transformers via Krohn-Rhodes in Ln et al. (2023b) do not
inherently length generalize. Both theoretical [Huang et al. 2024) and empirical research indicate difficulties in generalizing even for some simple star-free languages (Bhattamishaa et al. 2020 Liu et al. 2023a], Known geigth-eneralizing constructions are limited to very simple subclasses such as the piecewise testable languages (Yang and Chiang 2024]. In contrast, for SSMs we have a single model per language, at finite precision and for arbitrarily long inputs. Thus, expect that the SSM architecture confers an advantage in star-free state tracking problems when compared to transformers prediction we will find supported experimentally (Figure
3.4 SSMs can perform unbounded counting
Having characterized the regular languages modeled by SSMs, we now consider languages requir- ing unbounded counting (Fischer et al., 1968b), specifically, languages recognized by keeping track of one or more counters, where each character causes a specific increment or decrement to each counter [Krebs et al., 2015 Hahn et al. 2015 Weiss et al. 2018 Kutrib et al. 2021]. A prime ample is the Dyck-1 I language of forl-formed strings over "(" and ")"; here a counter is incremented (decremented) whenever opening (closing) bracket is encountered; string is well-formed if and only if the counter is at the end of the string. Some other relevant formal languages are Shuffle- Dyck-k (the shuffles of multiple Dyck-1 languages), a"b" here, a increments the counter and decrements it, and c" here, there are two counters, one keeping track of a" and one of b" (See Appendix C.2 Such counter languages are fundamental as basic context-free (Dyck-1, a²b") or
(e.g., d"b"c"") languages [Hopcroft et al. 2001]. and have been the subject of studies of both transformers [Bhattamishra al.) 2020 and RNNs [Weiss al. 2018
Theorem 5. The languages Dyck-1, ShuffleeDycckk n-ary Boolean Expressions, d²b", c"b and d" (defined in Appendix C.2 can each be predictively modeled by an SSM.
The proof is in Appendix B. Intuitively (Figure 2 an SSM can directly implement the required counters by setting = and by defining B(ea) to be the increment or decrement cased by a. In modeling such languages, SSMs pattern with both transformers [Bhattamishra et al. 2020 and LSTMs (Weiss et al. 2018).
It may seem counterintuitive that NONNEGATIVE SSMs can perform unbounded counting but (by Theorem 2 not modular counting- the latter would seem to just require reading out the value of an unbounded counter. What is key is that, even though h can encode unbounded counts, reading the modular value of an unbounded integer a formidable problem for typical neural network nonlincarities, in particular when the information has been pushed through normalization (
We should note that there is qualitative difference between this result and the preceding positive results about state languages (Theorems and 4. in that the construction in Theorem 5 uses unboundedly large entries in the state h, whereas Theorems and 4 use bounded values finite precision. Indeed, we will find better length generalization in the finite-state case (Figure
A consequence of Theorem is that SSMs can recognize some languages transcending the context- free languages, as "² is not context-free, second application of the theorem, of great linguistic interest, is to bounded hierarchical structure, as we discuss next.
7

---

3.5 Bounded Hierarchical Structure without Stacks
It is generally agreed that hierarchical structure is a key aspect of language, and comprehending lan- guage at human-like level requires the computational ability to process such structures [Chomsky) and Schützenberger 1963 Linzen et al. 2016) Everaert et al. 2015]. The fundamental data structure for the same is stack, where information is stored and removed as one traverses to higher and lower levels of hierarchical embedding [Hopcroft et al., 2001]. We now show that SSMs' counting ability can offer shortcuts on languages modeling hierarchical structure, eschewing the need for stack.
A useful abstraction of hierarchical structure as relevant to natural language the family of Dyck languages. The bounded-depto Dyck language Dyckk, with K types of parentheses and depth h is the language of well-bracketed strings over (1. )1. .... (x. 0g. such that the number of yet unclosed brackets never exceeds h in any prefix (Hewitt et al. 2020 Yao et al.) 2021b). The Chomsky- Schützenberger theorem [Chomsky and Schützenbergerr 1963] asserts that any context-free lan- guage can be expressed as a homomorphic image of the intersection between a Dyek language and a regular language. Specifically, the Dyck language question refers to the classical unbounded- depth Dyck language, where h - underscoring its fundamental role as the structural backbone of context- free languages. Bounding the depth reflects the fact that deep embedding is rare in natural language Karlsson 2007 Blasi et 2019). Prior work has found that two-layer transformers (Yao) jct al., 202 and traditional RNNs [Hewitt et al.] 2020, Bhattamishra et al. 2020 both model all Dyckg, & languages. The same turns out to hold for SSMs:
Theorem 6. There is a two-layer SSM with d = OhloggK) that predictively models Dyckk & at all imput lengths, at finite precision.
The proof is in Appendix B.5 Intuitively (Figure 3). the
Mamba SSM Layer Layer
first layer records the depth of each parenthesis using the ideas from 33 and the second layer keeps track of the last open bracket at each depth using Theorem T We note that, since Dyckg, a is star-free. Theorem already guarantees the existence of representing SSMs, but the depth and width guaranteed by Theorem is likely to be
(Dyck-(B, 10). Test)
Close Acouracy
0.8
0.8
much better than what would be obtained by black-box application of Theorem 4 As |Hewiitt et al. (2020) show, h llo K units is optimal up to constants and is attained by
0.4
Model
0.2
Layer Memba
Layer Mamba
traditional RNNs and LSTMs. The SSM construction is
very different from that of Hewitt et al.) [2020] for tra-
25
50
75
100
Memory Dimensions
ditional RNNs (both simple RNNS and LSTMs), which directly simulates stack. Our construction is similar to the transformer construction in Theorem 4.2 in Yao et al.) [ which however has to rely specific positional encodings, unlike the SSM construction. This highlights that stacks not the only way of simulating bounded hierarchical structure in recurrent architectures, and non- stack-based strategies can even attain the same optimal scaling of hidden units. Probing whether such stack-free shortcuts are learned by SSM-based LLMs is an exciting problem for future research.
Figure 4: As predicted by Theo- rem 6 Mamba with 2 layers can model Dyck(K, h). Results for test set with strings of length 700 S n S 1400.
4 Experiments
We have derived fine-grained theoretical characterization of expressiveness strengths and limita- tions of SSMs. We now show that our positive results can be instantiated and learned in a realistic SSM implementation, by evaluating recent highly successful SSM, Mamba (Gu and Dao 2023)
FlipFlop We empirically instantiate Theorem I using the dataset of Liu et al. 2023a reflecting
the language LFF as defined Section 3.1 Matching Figure 2 in Liu et al. [2023a]. we evaluated both on in-distribution data, and on out -istii-iittiiittio data where the distance between read and write instructions tended to be larger. We evaluate for predicting the bits following r instruction
Predictive modeling is trivial at other positions, only the input symbols need to be considered there.
8

---

[1. Accurscy
Accuracy
[51, Accuracy
100) Accuracy
Starfine Langungee
Courter
Pdff
Figure 5: Results on 27 formal languages, comparing our Mamba results (blue) with transformer results reported by Bhattamishra et al. [0200 (orange), on in-distribution lengths (solid) and out- of-distribution lengths (dotted). As predicted by Theorem[4] Mamba performs strongly star-free languages, and even shows perfect length generalization. Again as predicted by Theorem 44] per- forms poorly non-star-free languages. Results for transformers from Bhattamishra et al. (0200
are mixed. Mamba also succeeds on learning the counter languages from Theorem perfect accuracy at in-distribution lengths at in-distribution lengths, but length generalization lags behind transformers.
[]] showing
matching the "deterministic/clean" mode of Liu al. [023a]. and considered predictions to be correct only if all predictions within a sequence were correct. (Further details in Appendix D.2) small lne-laye Mamba model converged to 0 error in both validation sets after ~ 1400 steps (Figure 6), compared to 500 steps for an LSTM reported by Liu et al. (2023a). In contrast, Liu et al. 2023a found that transformers kept making occasional mistakes despite training for 10K steps.
Test Suite from Bhattamishra et al. 2020 To test
Layer Mamba SSM
our theoretical results on regular and counter languages (Theorems 2 4 5 we test Mamba on 27 formal lan-
Flip Flop Validation Set Performance
10a
guages, including 18 regular languages and 9 counter lan- guages, based on prior study comparing transformers and RNNs [Bhattamishra et al., 2020). The regular lan- guages include popular benchmark [Tomita] 1982 and
10-2
Test Eroo
10-4
various regular expressions; 11 are star-free. The counter languages include the languages covered by Theorem 5 (Definitions in Appendix C). We chose this test suite as it precisely covers Theorems 4 and 5 and we have proven (in)expressibility results for each language in the set.
Distribution (F.
10-6
FFL(C.98)
500
1000
Training llerations
Following [Bhattamishra et al. [2000], we trained the model for predictive modeling. i.e., at each step, the model outputs a label indicating the set of possible next characters (3), including EOS when required. Following Bhattamishra al. [2020), we count the model's I's response on an input string as correct and only if predictive mod- elling successful at all positions in the input. Such a evaluation setup makes random baselines low, where a random predictor would have accuracy exponentially small in N in each of the positions. Training inputs have length in [1,50]; the model is evaluated on held-out bins with length [1,50] and [51,100]. Further experimental details are in Appendix [.]
Figure 6: Test error on the validation set for LFF. following Liu et al.) [2023a]. Mamba shows near-zero test eтror in both In- (green) and Out-of-distribbtiion (orange) settings, consistent with The- orem D and avoids the failure seen in transformers [Liu et al. 2023a
We show our Mamba results, together with Transformer results reported by Bhattamishra et al. (2020). in Figure 5) LSTMs perform perfectly on all languages, and are thus not shown. In striking confirmation of Thcorem 4 Mamba learns all star-free languages with strong length gener- alization but performs poorly
non-star-free languages. Transformers show more mixed results, often failing to length-ge gength--eeerrlize even on star-free languages. Consistent with Theorem [5). Mamba, like Transformers, learns counter languages but struggles more with length generalization. The dif- ferences in Mamba's 's performance between star-free and counter languages may stem from the fact
4 *Theorem 1 constructs a two-layer SSM. We hypothesize that Mamba uses its local convolution (Remark replace the lower layer from the construction in Theorem I

---

that the construction for the former class (Theorem 4 is able to use finite precision and bounded state values at arbitrary input lengths, while the latter (Theorem
uses unbounded state values. 5
Bounded Hierarchical Structure To test Theorem 6 we recreate the experimental setup from
Yao et al. [021bb. Matching their Figure 4, we trained Mamba to predictively model Dyckk, & at K and h -= 10. The training and the validation set contained samples of length & 700, while the test set contained samples of length 700 I n S 1400. Yao al. [2021b] found both transformers and LSTMs achieved strong performance on this setup. We provide further details in Appendix (D3
Recall that Theorem shows that two-layer SSMs can predictively model Dyckg We tramed Mamba with 1 or 2 layers and varying dimensionality. finding that two layers can achieve essentially perfect performance across model sizes, even on the test set (Figure 4 and
5
Discussion
Related Work Our work belongs to an incipient line of research into the expressiveness of SSMs
(Jelassi et al. 2024 Merrill al., 2024]. It closely related to a long string of work studying the
expressive capacity of neural sequence models, which has so far focused on recurrent networks [e.g.
Siegelman and Sontag 1995 Bhattamishra et al., 2020 Hewitt et al., 2020] and. more recently, self attention [c.g. (Chiang et al. 2023 Merrill and Sabharwal 2023 Strobl et al. [0244]. A second link the classical and long-standing study of linear dynamical systems and control theory [Kalman 1960]. For instance, Theorem 2 relies the asymptotic convergence of an SSM on certain inputs, establishing link to the asymptotics of linear systems [e.g. Phillips and Solo 1992].
Take-Aways While theoretical in nature, our results have several actionable implications for SSM and LLM research, informing the rapidly growing research SSM-based L.MMs. First, encourag- ingly. SSMs can keep track of bounded hierarchical structure with optimal memory even without explicitly implementing stack (Theorem (6). suggesting that simple diagonal linear state updates may be sufficiently powerful for modeling the hierarchical structure of language. Second, SSMs resolve basic failure mode of self-attention in flip-flop state tracking while being parallellizable (Theorem D. Overall, SSMs and attention have overlapping but distinct strengths. This lends sup- port the development of hybrid architectures interleaving SSM and attention layers, instantiated very recently by Jamba [Lieber et al. [024]. Third, nonnegative gates as obtained by exponential or sigmoid parameterizations provably restrict expressive capacity, even in non-time-invarian SSMs (Theorem 2. While and Dao 2023 found no evidence that complex- vvalued paramerizations im- proved over real-valued ones in the language modality, our results suggest revisiting this question, at least for tasks where periodic state-tracking abilities may be important. Fourth, while exactly char- acterizing the capacity of transformers has proven difficult even in the finite-state case, Theorem 4 provides decidable characterization of the regular languages equivalently, finite-state tracking problems - that SSMs such as Mamba can model. Such decidable characterizations may make it easier to theoretically predict abilities and anticipate failures of LLMs; exploring the implications of this characterization in more realistic setups is an exciting direction for future research.
Limitations The main limitation of our theoretical results is that they focus on in-principle expres- siveness, and do not directly make statements about learning and generalization. Future work could address this, for example, by examining whether our constructions result in reasonably flat minima, or by studying gradient flow dynamics. While we empirically verified that our positive results can indeed be instantiated, in learnable manner, in one realistic SSM implementation. implementa- tional differences might still result in practical differences between implementations. Studying the role of such implementational differences is an interesting problem for future work; we have made a first step by theoretically elucidating the implications of nonnegative gate values.
Conclusion
We have studied the expressive capacity of modern state space models (SSMs), through the lens of automata and formal languages. We have shown theoretically that SSMs can express star-free languages, range of counter languages, and bounded hierarchical structure. By providing rigorous results about the expressiveness of the SSM architecture, our results can provide guidance to work on SSM-based language models.
10

---

Acknowledgments
We thank Mark Rofin for useful discussion about Theorem and we thank anonymous reviewers for their helpful feedback. We gratefully acknowledge the insightful discussions with members of the FLaNN community which contributed to the ideas of this project. Funded by the Deutsche Forschungseemeinschatt (DFG, German Research Foundation) Project-ID 232722074 SFB 1102.
References
E. Akyürek, B. Wang, Y. Kim, and J. Andreas. In-context language learning: Architectures and algorithms. Forty-first International Conference on Machine Learning, 2024. URL https: //openrevice www.wew...w.ww..eeeeeee 32
J. Almeida. Finite semigroups and universal algebra, volume 3. World Scientific, 1995.
D. Angluin, D. Chiang, and A. Yang. Masked hard-attention transformers and boolean rasp recog- nize exactly the star-free languages. arXiv preprini arXiv:2310. 13897, 2023.
R. Arora, A. Basu, P. Mianjy, and A. Mukherjee. Understanding deep neural networks with rectified linear units. arXiv preprint arXiv:1611.01 2016.
J. L. Ba, J. R. Kiros, and G. E. Hinton. Layer normalization. stat, 1050:21, 2016.
D. A. M. Barrington, K. Compton, H. Straubing, and D. Thérien. Regular languages in NC1. Journal of Computer and System Sciences, 44(3):478-499, 1992.
S. Bhattamishra, K. Ahuja, and N. Goyal. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7096-7116, 2020.
S. Bhattamishra, M. Hahn, P. Blunsom, and V. Kanade. Separations in the representational capabil- ities of transformers and recurrent architectures. arXiv preprint arXiv:2406. 09347, 2024.
D. Blasi, R. Cotterell, L. Wolf-Sonkin, Stoll, Bickel, and M. Baroni. On the distribution of deep clausal embeddings: A large cross-linguistic study. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3938-3943, 2019.
Bradbury, S. Merity, C. Xiong, and R. Socher. Quasi-recurrent neural networks. In International Conference on Learning Representations, 2016.
D. Chiang and P. Cholak. Overcoming a theoretical limitation of self-attention. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguisties (Volume 1: Long Papers), pages (664,7664, 2022.
D. Chiang, P. Cholak, and A. Pillay. Tighter bounds on the expressivity of transformer encoders, In International Conference on Machine Learning, pages 5544 5544-5562. PMLR, 2023.
N. Chomsky, Syntactic structures, 1957.
N. Chomsky and M. P. Schützenbergeer. The algebraic theory of context-free languages. In Studies in Logic and the Foundations of Mathematics, volume 35, pages 118- 1611 Elsevier, 1963.
G. Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314 1989.
Y. N. Dauphin, A. Fan. M. Auli, and D. Grangier. Language modeling with gated convolutional networks. In International conference on machine learning, pages 933-941. PMLR, 2017.
S. De, S. L. Smith, A. Fernando, A. Botev, G. Muraru, A. Gu, R. Haroun, L. Berrada, Y. Chen, Freitas, and Ç. Gülçehre. Griffin: Mixing gated linear recurrences with local attention for efficient language models. CORR, abs/2402. 19427, 2024. doi: 10. 00.48550/ARXX1V2202..4427. URI. httph::/doo...
S. Srinivasan, G. Desjardins, A. Doucet, D. Budden, Y. W. Teh, R. Pascanu,
org /1. 485.48850055 a ax 2402 222 19427

---

G. Deletang, A. Ruoss, J. Grau-Moya, T. Genewein, L. K. Wenliang, E. Catt, C. Cundy, M. Hutter, S. Legg, Veness, al. Neural networks and the chomsky hierarchy. In The Eleventh Interna- lional Conference on Learning Representations, 2022.
S. Eilenberg. Automata, languages, and machines. Academic press, 1974.
J. L. Elman. Finding structure in time. Cognitive science, 14(2):1792211 79-1 1990.
M. B. Everaert, M. A. Huybregts, N. Chomsky, R. C. Berwick, and J. J. Bolhuis. Structures, not strings: linguistics as part of the cognitive sciences. Trends in cognitive sciences, 19(12):22-7743 2015.
C. Fischer, A. Meyer, and A. L. Rosenberg. Counter machines and counter languages. Mathe- matical systems theory, 2(3): Sep 1968a. ISSN 1433-0490. doi: 10. 00.1007/BF01194011
URL httpt::/tso....... org/ 10. 1007/BP0169411111
C. Fischer, A. R. Meyer, and A. L. Rosenberg. Counter machines and counter languages. Math. Syst. Theory, ((3):265-2833 1968b. doi: 10.1007/BF01694011 URL httts::/doi.orq//1
L007/3P01694011
D. Y. Fu, T. Dao, K. K. Saab, W. Thomas, Rudra, and C. Re. Hungry hungry hippos: To- wards language modeling with state space models. In The Eleventh International Conference Learning Reprexentations, 2023. URL
net mett/forrumid--Cooyyyyr
A. Ginzburg. Algebraic theory of automata. Academic Press, 1968.
A. Gu and T. Dao. Mamba: Linear-time sequence modeling with selective state spaces. CoRR, abs/2312.00752,, 2023. doi: 10448500ARKXIV.312.0077 arxiv.2312.000
URLpttpss: httttp::/ddi..or/1.......
A. Gu, T. Dao, S. Ermon, A. Rudra, and C. Ré. Hippo:
Recurrent memory with optimal polynomial projections. Advances in neural information processing systems, 33: 33:1474-1487, 2020.
A. Gu, K. Goel, and C. Re. Efficiently modeling long sequences with structured state spaces. In International Conference Learning Representations, 2021.
M. Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8: 1715 2020.
M. Hahn and M. Rofin. Why are sensitive functions hard for transformers? In L.-W. Ku, A. Martins, and V. Srikumar, editors. Proceedings of the 62nd Annual Meeting of the Association for Com- putational Linguistics (Volume 1: Long Papers), pages 14973-15008, Bangkok, Thailand, Aug. 2024. Association for Computational Linguistics. doi: 10.18653/v 1/202.../oo.......ooogggg wttp//////22.... acl-oo4....1............
URL
M. Hahn, A. Krebs, K. Lange, and M. Ludwig. Visibly counter languages and the structure of ne In G. F. Italiano, G. Pighizzini, and D. Sannella, editors, Mathematical Foundations of Computer Science 2015 40th International Symposium, MFCS 2015, Milan, Italy, August 24- 28, 2015, Proceedings, Part II, volume 9235 of Lecture Notes in Computer Science, pages 384- 394. Springer, 2015. doi: 48 054-0 32
0111//97788-662-4800555 32. URL https:://dan /ttp:s//ddoo.o/////// 10.
978 3- 662
Hewitr, M. Hahn, S. Ganguli, P. Liang, and C. D. Manning. Rnns can generate bounded hier- archical languages with optimal memory. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1978-2010, 2020.
Hochreiter and Schmidhuber. Long short-term memory, Neural Computation, 98):1735- 1997.
J. E. Hoperoft, R. Motwani, and J. D. Ullman. Introduction to automata theory, languages, and computation. ACM New York, NY, USA, 2001.
B. Horne and Hush. Bounds on the complexity of recurrent neural network implementations of finite state machines. Advances in neural information processing systems, 6, 1993.
12

---

X. Huang, A. Yang, S. Bhattamishra, Y. Sarrof, A. Krebs, H. Zhou. P. Nakkiran, and M. Hahn. A formal framework for understanding length generalization in transformers. arXiv preprint arXiv:2410.02140, 2024.
Indyk. Optimal simulation of automata by neural nets. Annual Symposium on Theoretical Aspects of Computer Science, pages 337-348. Springer, 1995.
Y. Ito. Approximation of continuous functions rd by linear combinations of shifted rotations of sigmoid function with and without scaling. Neural Networks, 5(1):105-115, 1992.
Jelassi, D. Brandfonbrener, S. M. Kakade, and E. Malach. Repeat after me: Transformers are better than state space models at copying, 2024.
R. Kalman. On the general theory of control systems. In Proceedings First International Confer- ence on Automatic Control, Moscow, USSR, pages 481-492, 1960.
R. E. Kalman. Mathematical description of linear dynamical systems. Journal of the Society for Industrial and Applied Mathematics, Series A: Control, 1(2):152-192, 1963.
Karlsson. Constraints on multiple center-embedding of clauses. Journal of Linguistics, 43(2): 365-392, 2007.
S. Kleene. Representationof events in nerve nets and finite automata. CE Shannon and J. McCarthy, 1951.
A. Krebs, K. Lange, and M. Ludwig. Visibly counter languages and constant depth circuits. In E. W. Mayr and N. Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science. STACS 2015, March 4-7, 2015, Garching. Germany, volume 30 of LIPles, pages 594-607. Schloss Dagstuhl Leeibmiz-Zeentumm für Informatik. 2015. doi: 10.4230/LIPICS. 20155.2015.594, URLptttss /attps://do.... org/ 42300.............. Cww.iccS..AACCSS 2015...2..1.999
K. Krohn and J. Rhodes. Algebraic theory of machines. i. prime decomposition theorem for finite semigroups and machines. Transactions of the American Mathematical Society, 116:450-464, 1965.
M. Kutrib, A. Malcher, and M. Wendlandt. Input-driven multi-counter automata. Theoretical Com- puter Science, 870:121-136, 2021.
Lei, Y. Zhang. S. I. Wang, H. Dai, and Y. Artzi Simple recurrent units for highly paralleliz- able recurrence. In E. Riloff, D. Chiang, J. Hockenmaier, and J. Tsujii, editors, Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 4470- 4481, Brussels, Belgium, Oct.-Nov. 2018. Association for Computational Linguistics. doi: 10.18653/v1/D18-111 URL
O. Lieber, B. Lenz, H. Bata, G. Cohen, J. Osin, I. Dalmedigos, E. Safahi, S. Meirom, Y. Be- linkov, S.
O. Abend, R. Alon, T. Asida, A. Bergman, R. Glozman, M. Gokhman, A. Manevich, N. Ratner, N. Rozen, E. Shwartz, M. Zusman, and Y. Shoham. Jamba: A hybrid transformer-mant language model, 2024.
T. Linzen, E. Dupoux, and Y. Goldberg. Assessing the ability of LSTMs to learn syntax-sensitive dependencies. Transactions of the Association for Computational Linguistics, 4:521-533 2016.
B. Liu, J. T. Ash, S. Goel, A. Krishnamurthy, and C. Zhang. Exposing attention glitches with flip-flop language modeling. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, Decem- ber 10 16, 2023, 2023a. htRL:tt::/// /tatt::://paprrs.. wwwpssppppss.aaap nips caper /:les//ppper/2222/mm 510ad30188bdcc5bee fefa
B. Liu, J. T. Ash, S. Goel, A. Krishnamurthy, and C. Zhang. Transformers learn shortcuts to au- tomata. The Eleventh International Conference on Learning Representations, 2023b. URL.
net/ http:p/wwwwie...tt..fooemm.eeeed
13

---

R. McNaughton and S. A. Papert. Seinter-Free Automata (MIT research monograph no. 65). The MIT Press, 1971.
H. Mehta, A. Gupta, A. Cutkosky, and B. Neyshabur. Long range language modeling via gated state spaces. In The Eleventh International Conference Learning Representations, 2023. URL
W. Merrill and A. Sabharwal. A logic for expressing log-precision transformers. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
W. Merrill, Petty, and A. Sabharwal. The illusion of state in state-space models. ICML, 2024.
A. Miller. Finitary models of language users. Handbook of mathematical psychology, 2, 1963.
A. Orvieto, L. Smith, A. Gu, A. Fernando, C. Gulcehre, R. Pascanu, and S. De. Resurrecting recurrent neural networks for long sequences. In International Conference Machine Learning, pages 26670-266699 PMLR, 2023.
A. Orvieto, S. De, C. Gulcehre, R. Pascanu, and S. L. Smith. Universality of linear recurrences followed by non-linear projections: Finite-width guarantees and benefits of complex eigenvalues. In Forty-first International Conference on Machine Learming, 2024.
B. Peng, S. Narayanan, and C. Papadimitriou. On limitations of the transformer architecture. In First Conference on Language Modeling, 2024. URL http:t/s///ggeeeeisseee////rrrrr KidynPuLNN
J. Pérez, J. Marinković, and P. Barceló. On the turing completeness of modern neural network architectures. In International Conference on Learning Representations, 2019.
P. C. Phillips and V. Solo. Asymptotics for linear processes. The Annals of Statistics, pages 971- 1001, 1992.
Z. Qin, S. Yang, W. Sun, X. Shen, D. Li, W. Sun, and Y. Zhong. HGRN2: Gated linear RNNs with state expansion. In First Conference on Language Modeling, 2024a. URL https: //openreviex htw.://vvwweeeeeeeeeeeee wttp://eeeeeeteoooeteeeem wtw.:r//oorumm.ddssssaaa.... d=y6SqbōfCSk
Z. Qin, S. Yang. and Y. Zhong. Hierarchically gated recurrent neural network for sequence modeling. Advances in Neural Information Processing Systems, 36, 2024b.
Sakarovitch. Elements of automata theory. Cambridge university press, 2009.
C. Sanford, D. Hsu, and M. Telgarsky. Representational strengths and limitations of transformers. Advances in Neural Information Processing Systems, 36. 2024.
M. P. Schüitzenberger. On finite monoids having only trivial subgroups. Inf. Control., 8(2):190-194 1965.
N. Shazeer. Glu variants improve transformer. arXiv preprint arXiv:2002.05202, 2020.
H. Siegelman and E. D. Sontag. On the computational power of neural nets. Journal of Computer and System Sciences, 50: 10:132-150, 1995.
H. T. Siegelmann. Neural networks and analog computation: beyond the Turing limit. Springer Science & Business Media, 1999.
H. Straubing. Finite automata, formal logic, and circuit complexity. Birkhaeuser, 1994.
L. Strobl. Average-hard hard attention transformers constant-depth uniform threshold circuits, 2023.
L. Strobl, W. Merrill, Weiss, D. Chiang, and D. Angluin What formal languages can transformers express? a survey. Transactions of the Association for Computational Linguistics, 12:543-561, 2024. doi: 10.1 10.1162/tacl.... a 00663. URL
www.aahhwwwooooooo./222222 tacl-1.30
Y. Sun, Dong, Huang, S. Ma, Y. Xia, J. Xue, Wang, and Wei. Retentive network: A successor to transformer for large language models. arXiv preprint 10Xi::2307.0861)
14

---

M. Suzgun, Y. Belinkov, and S. M. Shieber. On evaluating the generalization of Istm models in formal languages. Proceedings of the Society for Computation Linguistics (SCiL), pages 277- 286, 2019.
M. Tomita. Dynamic construction of sinite-state automata from examples using hill-climbing. In Proceedings of the Fourth Annual Conference of the Cognitive Science Society, pages 105-108, 1982.
T. D. Nuland. Noncompact uniform universal approximation. Neural Nenworks, 173:106181, 2024.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polo- sukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998 6008, 2017.
S. Wang and Q. Li. Stablessm: Alleviating the curse of memory in state-space models through stable reparameterization. arXiv preprint 1XX::22311.144955 2023.
Wang and B. Xue. State-space models with layer-wise nonlinearity are universal approximators with exponential decaying memory. Advances in Neural Information Processing Systems, 36, 2024.
G. Weiss, Y. Goldberg, and E. Yahav. On the practical computational power of finite precision mas for language recognition. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguisties ( (Volume 2: Short Papers), pages 740-745, 2018.
A. Yang and D. Chiang. Counting like transformers: Compiling temporal counting logic into softmax transformers. In First Conference on Language Modeling, 2024. URL https:// openrevi ew, met/forum d=FmhFg4UJ9K
S. Yang, B. Wang, Y. Shen, R. Panda, and Y. Kim. Gated linear attention transformers with hardware-efficient training. Forty-first International Conference on Machine Learning, 2024.
URL https: https:://ooenrevieee wetpeeewwwwwwweeeeeeeeeeeeeeeeee
S. Yao, B. Peng, C. Papadimitriou, and K. Narasimhan. Self-attention networks can process bounded hierarchical languages. In Proceedings of the 59th Anmual Meeting of the Association for Compu- tational Linguistics and the 11th International Joint Conference on Natural Language Processing ( (Volume 1: Long Papers). Association for Computational Linguistics, 2021a. doi: 18.18653/v1/ 2021. 2021 acl-llnl.g..... 292. htt.:tpppp.oo...oo..oo////11111/
292
Yao, Peng. C. Papadimitriou, and K. Narasimhan. Self-attention networks can process bounded hierarchical languages. In C. Zong, F. Xia, W. Li, and R. Navigli, editors, Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the I 11th International Joint Conference Natural Language Processing (Volume 1: Long Papers), pages 3770-3785, Online, Aug. 2021b. Association for Computational Linguistics. doi: 10. 10.18653/v1/2011 hwwp:////2......og..22.....
ogy. ogg.oog/yy...22.11 .ac long. 292
A. Yu, A. Nigmetov, D. Morozov, M. W. Mahoney, and N. B. Erichson. Robustifying state-space models for long sequences via approximate diagonalization. arXiv preprint arXiv:2310.01698, 2023.
B. Zhang and R. Sennrich. Root mean square layer normalization. Advances in Neural Information Processing Systems, 32, 2019.
N. Zubić, F. Soldá, A. Sulser, and D. Scaramuzza. Limits of deep learning: Sequence modeling through the lens of complexity theory. arXiv preprint arXiv:2405. 16674, 2024.
15

---

A Instantiations of General Framework in SSM Models
Here, survey how 1 is instantiated in range of SSMs. As stated in Section 2.1 we refer to SSMs where the gate A does not depend on X as fime-invariant. An equivalent terminology the distinction between "Weak Linear Time Invariant Convolutional Models" (i.e., time-invariant) and "Linear Time Variant Models" (i.e., non-time-invarian) in Akyürek et al. [2024]
A.1 Non-Time-Invarian Models
Approximately simultaneously with or more recently than Gu and Dao
2023 range of non-time-
invariant SSMs have been introduced (De et al.) 2024 Yang et al,4
Qin et al. 2024b a This
category also covers highly similar earlier RNN variants [Bradbury et al. 2016 Lei ct al. 2018
Mamba In Mamba, (2) and (3) directly map onto Eqs. (2a) and (2b) in Gu and Dao 2023 The notation of Gu and Dao 2023] use matrix multiplication A instead of elementwise mu pica-llcaa- tion Axx h in (REF), but importantly, Mamba's 's diagonal, so we can take A A(x;), ) Ag. Due to exponential parameterization, its entries are nonnegative.
Griffin The RG-LRU layer of Griffin
De al.
2024
the equation
h
=
oh +
at o (1)
A(x))
B(x)
where 4;4 neurally parameterized in terms of x, but not her by design, a, (0, 6 instan- tiated in terms of linear transformations, GeL.U, and RMSNorm (Figure 2 in De et al. (2024). ). The local attention used by Griffin can be subsumed into SSM layer (Remark
Gated Linear Attention [GLA Yang al. 2024) This model (Section 4.4 in Yang et al. 2024]
instantiates our framework using recurrence of the form (T); while the state two-dimensional in this model, the update is performed by elementwise products as in [T]. The gate is obtained by applying sigmoid to linear transformation of xy; thus, its entries in (0, 1). @ is instantiated in terms of SwiGLU and LayerNorm.
HGRN HGRN IQin et al., 2024b] and HGRN2 [Qin et al., 2024a are defined by a recurrence of the form ( the gate entries are (0,1) by design. i is instantiated in terms of GLU, linear transformations, and normalization. In HGRN, the state is complex, but crucially the gate remains real-valued.
A.2 Time-Invariant Models
Appendix B), such [Mehta al. 2023 Sun et al. 2023 Orvieto et al. 2023). Time-invariant SSMs have often used complex-valued states and gates; this does not have major impact on our results: First, as complex-valued SSMs subsume real-valued ones, our positive results carry over. Second, our negative result about PARITY is affected by this distinction and requires a separate argument, see Theorem
Time-invariant SSMs introduced before late 2023 are surveyed by Gu and Dao 2023
Note also that Aht, is often described as a general matrix multiplication, but diagonalizable (e.g. Lemma 3.2 in Gu al. [202T]; (Sun et al. [2023] for RetNet), which eeven though imple- mentation may be based on non-diagonalized representations [Gu et al. 2021 renders the model equivalent one where is diagonal from the start. This equivalence shown Lemma 3.1 in Gu lt al. 2021].
B Formal Definitions and Proofs
B.1 Flip Flop
We begin by introducing key notions of automata theory. References for automata theory include
Filenberg 1974), Hoperoft et al. 2001) Sakarovitch (2099) We will provide those key notions that
16

---

are necessary to prove our results. We will focus on deterministic finie--tate-auton (DFA), and simply refer to them as finite- state-attttaa "tate-automata" First,
Definition 7. A (deterministic) finite minit-state-automannd automaton A consists of:
a finite alphabet Σ
a finite state set Q
a starting state qo E Q
transition function xxx-~x
We extend u to a map u: x + +Qh by sefting:
u(q, =4
u(q.wI...14) = u(u(q. w w/11)
where e is the empty word.
Intuitively, u(qo, w) the state that A is after reading w.
The automaton recognizes a language L - if there is a recognizing set R C Q such that
L:= {w u(qo, w) R}
(4)
Kleene's Theorem Kleene 1951 asserts that language L S Σ" is regular (i.c., defined by a regular expression) if and only if it is recognized by some sinite-state automaton.
A very fundamental automaton underlying Flip Flop is:
Definition 8. A set-reset automaton is seate-state-uutommaite where (gMg))) C E and
i
u(q. a)
[
(5)
else
Intuitively, such an automaton keeps recording the last seen symbol from a designated set Q Σ. Such an automaton is easily simulated with single non-time-invariant SSM layer:
Lemma 9. Let A (2,2.q qn. u) by a set-reset automaton. Then there is single-layer SSM with finite precision and width d = 1 log that maps each WI..T E. the state sequence u(go, u((0,, w12),..., u(qo, WI..T) E Q
Formally, there is an injective map V Q > Rdd such that p(z.) = V (u(loo fort 1
Proof. Let B(G) E TRlogl@1 be a binary encoding if E Q, and Rlogio else. Take hg = B(qo). Let A(o) 0 if G Q and A(o) else. After processing string, the state h, is B(o) where the last symbol in Q that has occurred if any has, and B(qo) otherwise. Coming to (2 in order to avoid division by zero when normalizing if no element of Q has been read, we add dummy dimension to 14 whose value is always 1. We take Mix; Mix; to be the identity. Note that, even though normalization will affect the numerical values, the binary encoding of a
still be read
out with finite precision, < [|4112 < /I log Q], and thus nonzero entries will remain bounded away from zero
Theorem 10 (Restated from Theorem all lengths, at finite precision.
D.. There is a two-layer SSM that predictively models LeF at
Proof. In the first layer, we use Lemma 9 to simulate a set-reset automaton over the input alpha- bet Σ₁ [w, i,,r,,,0111 1) where Q: Σ, U {go)- This layer outputs at each position whether the last instruction was write, read, or ignore. The layer additionally, at each position, forwards the input symbol using additional dimensions. Formally, at the first layer, p(h,) allows to read out the input symbols 1, Σ.
5 A closely related notion is the semiautomaton, which is the notion considered the closely related work Liu et al, (2023b) Semiautomata lack fixed start state go. We include 4o. but this difference is not substantial for formal results.
17

---

In the second layer, we again use Lemma 9 to simulate a set-reset automaton over an extended alphabet Σσ == x Σ,, where the first component indicates the imput symbol x, and where the second component indicates x,-1. In this set-reset automaton, Q2 contains, besides a start state go, those elements of Σg whose second entry w. The second layer thus keeps track of the input bit b E (0, } following the last write instruction. It additionally forwards the input symbol X; using additional dimensions.
The second layer, via p. then predicts the possible next symbols on the basis of this information: If X, {0. I), any instruction in fw.r, is possible. If,, E {w.?]. any bit in {0. 13 is possible. xf = the bit stored after the last write instruction is possible; if no write instruction has appeared (hence, the second automaton is still in its start state), any bit in {0, possible.
B.2 Difficulty of Representing PARITY
Definition 11. PARITY is the regular language over Σ (0,1) of strings where the number of ones even. As a regular expression, PARITY is (0' 10")"
Theorem 12 (Restated from Theorem 2 No SSM satisfying NONNEGATIVE can recognize PARITY al arbitrary input lengths with finite precision.
Proof. We consider an SSM with multiple layers, and indicate the layer in superscript: h2 .-... ....,,,!). An!0) We write for the input token embedding e(w,). Consider a SSM processing the word I', for I We show, by induction over the number of layers, the following claim:
(+) Each entry of 2 converges to a value bounded, in absolute value, by a constant.
By the assumption of finite precision, convergence automatically leads to the entries becoming ul- timately constant. Once we have shown this, we know that ze constant when r is sufficiently large; thus, the parity of the string 1' cannot be read out from zi As consequence, the SSM cannot recognize PARITY. Indeed, we have shwon the stronger claim that the language (11)* the language of even-length strings over one symbol is not recognized by an SSM; we will use this stronger statement in Corollary|] [4]
We proceed to proving (t). The claim (+) is trivially true at = 0, as the input token is always the
same and we defined 2t : e(w;). Now consider By hypothesis, the activations are given as
(0)
h
(8) B(x;)
(6)
where Bxx) are constant a = A(x:) B := B(x,) when / > To. for some To > 0. The solution of the recurrence for To is
bro + a aa-11 .
B
h -To
1-a
Each dimension j I....., d of this vector can be constant (if (hr,); + a.-1 = 0), diverge exponen- tially (a, > 1), converge exponentially (a, < 1) or diverge linearly (a, 1).
We next need to show that & Mixe (NommMMxx (b), converges.
First, consider the effect of applying a linear transformation to the state h, Each entry of the result will be some linear combination
24 (h;) + ... (h:))
If each a < 1, then N, converges. If some la, 1, there may be some cancellation if a; O, for some i * j: cancellation can only lead to full erasure of the relevant terms or to a remaining term with the same exponent. In conclusion, each entry μ, will again either converge to finite value or diverge towards #o0.
We now need to understand the behavior of Mix (h),))) Recall that, based our survey (Ap- pendix A), we allowed it to contain linear, GLU (Dauphin et al. [017], and SwiGLU (Shazeer) 2020 components. If Mix, (h,,,; implements linear transformation only, each entry likewise may
18

---

converge. diverge linearly, or diverge exponentially. We note that a is the sigmoid function (u,) always converges, as o simply saturates to 0 if u, diverges. Hence, if Mix, (h,,,, imple- ments GLU, each entry likewise may converge, diverge linearly, or diverge exponentially. Finally, Mix, (h,,x) implements SwiGLU, each entry of the result will be a product of linear com- bination of the form 4, and SwishB applied to another such linear combination. Depending on the behavior of these two u,-like terms, the outcome will behave as a product of sequences that may con- verge exponentially, diverge exponentially, or diverge linearly e.g., the outcome may also diverge quadratically, or converge as na etc.
If all dimensions of Mix xx) converge, then Norm (h,,)) will also converge to scaled version of _ scaled by a bounded factor as Bi + O. Now assume some dimensions of Mix (h), do not converge; in this case, for any two dimensions i, j. either their ratio will converge to constant, or converge to 0 or t After applying Norm(-). the entries asymptotically dominating the others will converge to finite value bounded, in absolute value, by 1; the others will converge zero.
In conclusion, we have found that each entry of Norm(Mix, (h), converges to some number bounded, in absolute value, by 1. As Mix; is continuous, each entry of 2 likewise converges, with bound depending on the Lipschitz constant of Mix2.
We next show the result, referenced in the main paper text after Theorem about time-invariant SSMs with complex-valuee gates:
Theorem 13. TIME-INVARIANT SSMs cannot recognize PARITY with finite precision at arbitrary input lengths, even with complex-valued gates, as long as each entry in each has rational angle in the complex plane.
Here, by rational angle, refer to angle that is rational number when expressed in degrees; such angles are rational multiples of 2n when expressed in radians. As the rational angles are dense in the reals, solutions would be very hard to find in particular given that irrational numbers are not exactly represented in finite precision.
expects that even if some irrational angles permitted modeling PARITY, such
Proof. By assumption, any A E C in any layer can be written as
Aj r)exp(2niiq)
where 9j E [0, 1] is rational and r; 2 0 is real here, 2nq, known as the argument of Aj; describes the angle of A, in the complex plane in radians. Correspondingly, the angle in degrees is described by qj 360 this rational if and only if qj is.
As time-invariant SSM has a finite number of such values A,, across all its layers, we can select a positive integer W such that Waj E N for each j. in each layer. Importantly, (A,) (r;)" E R.
Now consider the action of any layer of the SSM on an input sequence of the form Ar = (10 -17.
The claim is that, for each == 1,...,.. W. the sequence
(R) 7W++
(10)
converges f -> oo. As in the proof of Theorem 2 in the finite-precisie setting, converge entails that the sequence becomes ultimately stationary. Note that the parity of Ar equals the parity of T;
(K) hence, it is impossible to read out the parity from 27W when 7 is large.
19

---

Now consider, suppressing the index for the dimension in 1.....:: d:
kW
B(2 11
W
WW
B(
11-1)1
Σ
Σ
( Bi -I=((z+
j=
W-
Σ
E
A
[r-3)W
(1-))--B(2((t-- (B(((k+t))
Σ
(A-1)
Σ
Σ
, S- eexp(-22xx
25i j4) B (z, (
f
Σ
exp(-2nri (2
Σ
[(--)) -jj B( (k-11)
++
Separately considering summation beyond To at which (k-1) 2W+] has become stationary, we get
W
Σ
exp( 2 )r
Σ -
Ui
U2
U1 and U2 do not depend on Intuitively, U2 E C determines direction in the complex plane, whereas U3 E IR determines magnitude. It remains understand U3. which can be rewritten as:
U33 Σ -o- " - (
r 1
(11)
==0
T=1
We have now achieved a situation like in the proof of Theorem 2 diverge linearly, or diverge exponentially. The remainder of the proof is analogous to that proof.
Uz converge exponentially,
O
The following Corollary of Theorem will be used in the proof of Theorem
Corollary 14. Assume NONNEGATIVE, SSMs with finite precision cannot recognize any non-star- free regular language.
Proof. For any non-star-free regular language L, there are words u, v,w such that the membership uv" E L is determined by the value of n modulo some finite integer (depending on L) MMc- Naughton and Papert 1971. Fix any such u, E.
Now assume an SSM satisfying NONNEGATIVE can recognize with finite precision. We can subsume the action of into the state ho by taking ho. in each layer, be the state of the SSM after reading u. We now have an SSM that can determine the parity of I when fed a word of the form w.w
For this SSM, we want to show
(+) When fed words of the form v,v2 _,,,.... ,..., for each i 0,..., ||] 1, and each layer k 1 1.
(K) the sequence 2///4: converges as 1 +
20

---

As in the preceding two proofs in this section, convergence entails becoming ultimately constant in the mitte-preciioon setting.
The claim (t) is immediate at k = O.
Now at k > 0, we write:
(8) ///p/+
= A(2////t) ... A 1k-1)
(1-11)
(K)
1| G 1]|++i
(1-11) ... Al 1)//++++2 )B B
(k
A (<//)t+) ... 11 (8-
(k-1)
11+++ ) (11j-1]]x|+++
(k-1)
B(2 1)1oo++
(k-1)
On the RHS, as f + 0, all terms except for 1)-+)) become constant by the inductive hypothesis. Hence, there some a. B such that, for sufficiently large 1.
(A) /|/++ = a h DI +B
(12)
We are now, for each in the same situation as the proof of Theorem 2 recurrence can converge exponentially, diverge exponentially, or diverge linearly; as in that proof,
each dimension this
follows that _()
*r/v|+2 converges as t - oo,
We have shown (t).
We now follow up by showing that
(+) When words of the form v' w. for each i= //.., and each layer = I....,,, L, the sequence (k)
c/pl+z converges f
Again, at finite precision, convergence entails that the sequences are ultimately constant. Again, (+) true at k = trivially. When feeding the SSM words of the form v' Vw, in each layer, the final state in each layer k, at each i = -1, 1,...,/wi |w]:
AZ (k-1)
A...((///tt) (2/11-1) /
MM++
+ Az/////tt) ((/(--1)) A A(////t )B (((2))1+1)
(k-1) (k-1))
+...
+ +B( (8-1)
By inductive hypothesis, for large 1, there are Vr such that v o
+%
(k) and, as shown before, each entry of h tly converges exponentially, diverges exponentially, diverges
linearly. Now, by assumption, one can read out, at finite precisiion, the parity of from
+///+|/| Mix, (Norm mi
(ul+ +%w )))
(8)
We now simply absorb the operation X + 1/nl X +Ywi into Mix2, and obtain by the same arguments
as in the proof of Theorem that (L)
[// converges as r - co. This is contradiction to the claim that the value of can read out, modulo k, from (1.) [//[+|// at finite precision.
Remark 15. As outlined in our analysis, the assumptions in Theorem are based on layer-wise op- erations that are either linear or based on the GLU or SwiGLU activation functions. This assump- tion is critical the proof: one could design activation functions that make PARITY expressible.
21

---

Given a sequence x= XT,, consider the function f(x) 1--1 This continuous function is even, and f(x) O
is designed to satisfy the condition that, for bit-strings x. f(x) 11 Ei -i otherwise. At first glance, it seems like this function can be approximated by cumulative sum layer in combination with a two-layer SSM compute _ 11
However, this construction cannot be implemented under the condition for which we prove Theorem 2 This is because computing this function fxx inherently requires a layer-wise nonlinear operation (such as MLP) capable of representing sine and cosine functions over arbitrarily large imput values. Importantly, achieving construction that works for any input length requires the ability to handle urbitrarily large inputs within a single operation.
A single GLU or SwiGLU activation function, or even a more classical MLP with ReLU or sigmoid activations, is not expected to represent sine and cosine functions over unbounded inputs. The reason for this limitation lies in the universal approximation results for feedforward networks. These results generally guarantee approximation within compact convergence on bounded sets, such as in the compactification of R or in L! spaces, as described in Cybenko [1989), Ito 1992), and Arora et al.) (2016]. None of these results extend to uniform approximation of sine or cosine over the entire real line.
Recent work by van Nuland (2024) addresses the universal approximation capabilities in the space (R),, which is the class of bounded continuous functions over R. This result is particularly relevant since approximating sine and cosine functions uniformly over R would fall under this category. According to their Proposition 5.5, sine and cosine functions cannot be uniformly approximated using certain activation functions, limiting the feasibility of approximating f(x) 2 in rypical MLP architecture.
Thus, it is unrealistic to expect a typical MLP, with ReLU sigmoid activations, to implement the function f(x)= = +1 uniformly for arbitrarily large inputs. Consequently, construction based on such a function would either necessitate custom activation functions, such as periodic activations specifically designed to handle sine and cosine, or require the size of the model to scale with the input length. Either solution removes apparent contradiction with Theorem 2 fall outside the scope of the ussumptions made in our proof.
as these adjustments
Wang and Xue (2024) and Orvieto et al. (2024) provide universal approximation guarantees for SSMs, but these guarantees depend on the size of the approximating network growing with input length. This dependency is clearly stated in Proposition 3.6 and Proposition 3.9 Wang and Xue [2024), and further emphasized by Orvieto al. (2024]. in their Remark 2. Our results, in contrast, pertain to the existence of a single SSM capable of recognizing formal language for any input length, independent of network size. Thus, such universal approximation results do not undermine Theorem
B.3 Proof of Theorem 4
Our proof of Theorem 4 will rely the algebraic theory of finite automata, specifically the cascade Theorem [Krohn and Rhodes 1965]. These techniques, originally developed in the 1960s, have recently been introduced to the theoretical study of transformers by Liu et al. 2023b); we provide self-contained definitions and somewhat different notation, tailored to our proofs about state-space models. In general, we will find that the properties of state-space models allow more natural and directly length- -enttiignneraliiing implementations of these algebraic notions than what is possible for transfomers.
product and the
Recall the definition of a finitestate-automatton (Definition 7p. Our construction will build on an important operation automata, the cascade product [Krohn and Rhodes 1965 Eilenberg 1974
Ginzburg 1968]:
Definition 16. Given two automata A,, A2 with associated alphabets Σ,, E2 and state sets Qr Q2 such that
= Q1 x Σ1,
(13)
the cascade product Ag (Ai is the automaton given by
. E
22

---

0 Q2 x Q1
qo is the tuple of the starting states of Ag A
u( (q. p). = (u2 (q. (p) , (p.G))
We note that the literature usually uses "o" for the cascade product [e.g. Eilenberg 1974]. To avoid collision with the elementwise product "o" (e.g.. (I)), we here instead use "?", usually used for the wreath product- - a product on monoids with an effect analogous to the cascade product [Almeida] 1995].
While the formal definition is cumbersome, the intuition behind it is simple: The cascade product corresponds to first reading a word w with Al recording the state sequence qo, .1.............................. 9 = and at each / = . ww|-pasting the state q-1 together with the input symbol w; E Σ resulting in a word over a new alphabet Q1 Σt, and then running A2 on the resulting word. The overall state of A2lAi after reading a word is the tuple of the states reached by A and A₁. Note that we write Ag AA, rather than, A 2A2, because the second argument of the cascade product (A₁) intuitively reads the input first. preprocessing it for the other automaton, A the cascade product can thus be viewed as a kind of function composition.
The somewhat inscrutable update rule for u(::)) encodes the action of Ai in the second component, and the action of A2 the extended alphabet in the first component. There is close analogy the stacking of sequence models, and we will leverage this analogy to translate cascade products into multilayer SSMs. The fundamental background here is the following classical fact:
Fact 17 (Consequence of Krohn-Rhoder Theorem [Krohn and Rhodes 1965) and Schützenberger's Theorem [Schützenberger [9655). ) Each star-free regular language is recognized by an iterated cas- cade product of set-resei automata, (A)....)) Am--1) An, where each A, a set-rexet automaton.
This result follows from the Krohn-Rhoder decomposition theorem [Krohn and Rhodes 1965], which states that any finite-state automaton can be expressed as an iterated cascade product of sim- ple automata, specifically finite simple groups and reset automata. Moreover, Schützenberger's Theorem (Schützenberger 1965] characterizes star-free regular languages as those whose syntactic monoids are aperiodic, meaning they contain no nontrivial groups. Therefore, the decomposition for star-free languages involves only set-reset automata, leading to the stated cascade product structure. We now formally show that cascade products can be translated to SSM stacking. We need an auxil- iary lemma, which provides single-layer SSM that encodes the input w in state h, will use it to forward information about the state of Ag at 1 to A at r:
Lemma 18. Let Σ be an alphabet, and consider words E E", There is a one-layer SSM with = 4|E such that, for = 2..... [w], the character W can be read out from 2, at finite precision.
To prove Lemma 18 first idea is to use exponential moving average with A 11/2 encode the recent input characters in h;; this effectively encodes the full history into the binary expansion of ht, and in particular allows reading out the second-last input in principle. However, such a construction does not work at finite precision, because rounding may make it impossible to extract even the ceoond-mos--signffiaat bit @ We avoid this problem simply by taking A = 1/4, effectively utilizing only every two digits in the binary expansion of h, ensuring that the second- last input can be read out a constant margin. We now provide the formal proof:
Proof. We begin by showing the claim in the special case = {1,0}. Here, we take d = 4, and
hn 10,0,0,0²
A(eo) = [1/4, 0/
A(e;) = [1/4,1/4.0,0]
B(eo) = 1,,7
B(e1) = 1,0
IInformally in binary, 0.0111111...111 and 0.1 arbitrarily close.
23

---

Now we separately consider the state h, depending on the form of the prefix WI... (here wi.... refers 00 (the last characters of the prefix are 00), then
first r characters the word). If Wi...
E [ 00 1 1/8
h
(14)
0
because
h A(eo) h
(1,00,1,00 +1,00,1,0|'
to (h
To (
By definition A and B, each entry h is in [0,2]; the claim 14 then follows. If w1... ".......... then, by similar calculation
E [1. 1.25
E 1//4
(15)
In particular, assuming O, one can read off w4-1 from (h,)2 with margin of size 1/8. As w; is encoded in h, and due to symmetry, analogous statements hold when w, =
Now, for each a E E. we run such a one-layer SSM where represents a and 1 represents all other characters By running these in parallel (i.e. executing these operations with the same SSM layer simultaneously. utilising the width of the SSM layer) we obtain an SSM with d= 4/E] from whose states one can read out W finite precision.
the entries in h, are all bounded by 2, we find ||y ll S 2 independent of f, and the margin still bounded away from zero after normalization, and thus in 2,, where we can assume Mix,, Mix; to be the identity.
Gu and Dao 2023| or local attention [De al. 2024]. which aggregate information from local window some width >> O. These do not increase the expressive capacity beyond SSMs as we have defined in ( as aggregation of local information can be simulated with single SSM layer: Using the layer constructed the proof of Lemma 18 given the state hG, once one has read out w,-1 as described in the proof, one can recover h from h and x; then inductively read out w using h and x etc. Thus, to any given width A >> 0, one can read out Wt W W;-1 from the state h of this layer at finite precision.
Remark 19. Some SSMs include local convolutions [e.g. Fu et al. 2023
We are now ready to translate cascade products into SSM stacking:
Lemma 20. Let A, Ag be two inite-staae-autommal and assume that there are two SSMs with top-level states 2(41.) and (la.2) that map each w to the state sequences under A,, Az, al finite precision.
Formally, on word w, ((..))))) and (2(221222) provide the state sequences of A,, Az.
Then there is SSM with L1 + L2 layers that maps each w to the state sequence under Ag Ao. again at finte precision.
We that conceptually related result holds for transformers [Lemma 12 in Liu al. 2023b However, SSMs allow a simpler and length-independeer construction, as they do not require posi- tional encodings implement such a construction.
In fact, using binary encoding of Σ, achieve d = 4log Σ].

---

Proof. The lower layers are based on the SSM modeling 4, We duplicate each channel, so we now have 2d dimensions. We further add d further dimensions that directly pass on the input embeddings, i.e., A 0, B = Mix; = ld on these dimensions.
In the resulting SSM, / indicates both w; itself, and the state reached by A after reading wI...-- The state is redundantly indicated by two separate sets of d dimensions; the character w, is indicated by d further state.
Note, however, that the second automaton in the cascade product requires access to the state q--1 rather than gt-
For this, we add a layer provided by Lemma 18 of width 4|2). Additional 2d dimensions pass on (I) w,, and (2) the state that Ai reaches after reading the prefix Wi...-
We now have LI + 1 layers where 4 _/11 has 2d + 4 dimensions and indicates (1) wr. (2) the state that A reaches after reading the prefix wi...,, (3) the state that Al reaches after reading the prefix W1...-1.
The first and third piece of information are fed into the second SSM; the second piece is passed on in d additional dimensions. As we allowed A and B to be arbitrary functions, we redefine these in the lowest layer of that second SSM to read out from the dimeensisll component indicating (3), providing the desired second-to-lass state.
We have constructed an SSM with 4 + L2 + layers, where L + indicates (1) w/. (2) the state that Ag reaches after reading the prefix Wi..., (3) the state that A reaches after reading the prefix W1... pasted with the state sequence of 2j. This information is sufficient for reading out the state sequence of A9.
Note that the number of channels may not be consistent, as 3d in the top and bottom parts, but 2d 4 Q in the middle; simply pad to the larger dimensionality.
We now ready show the existence of length-generalizinn SSMs for any star-free state tracking problem, and conclude with the theorem:
Theorem 21 (Restated from Theorem 4). Let L be a regular language. The following are equiva- lent:
1. There is an SSM satisfying NONNEGATIVE that predictively models L at all input lengths, at finite precision
2. L is star-free.
Proof. We need to show:
SSMs at finite precision can predictively model all star-free languages. For each language, single SSMs is applicable at arbitrary lengths.
2. Assuming NONNEGATIVE, finite-precision SSMs cannot recognize any con-sttr--rree reg- ular language.
The second statement is Corollary 14 it suffices to prove the first statement.
Assume L is star-free. By the Krohn-Rhodes theorem, there is an automaton A that is a cascade product of some set-reset automata that recognizes L. By Lemmas and 20 there is an SSM that computes the state sequence of that automaton.
Now note that, since A recognizes L, the state g after reading w is sufficient for determining the set of characters that can follow this prefix in any element of L. For, assume otherwise, then there words w' such that u(go, w) u(go, w') and Σ such that woΣ* n * 0 but w' U 0; then u( u(go, wo) = u(go, w'o) but the set R is reachable from u(qo. wo) but not u(qn. w G), contradiction.
Hence, the SSM's outputs can be transformed, by composing p with a map from states to next- character sets, to predictively model L.
25

---

Theorem 22. SSMs with complex-valued coefficients evading both NONNEGATIVE and TIME- INVARIANT can represent all regular languages known be in TC
We we do not use this theorem in the main paper, due to the nonexistence (as far as we know) of implemented SSMs with this property.
Proof. SSMs evading both NONNEGATIVE and TIME-INVARIAN can count modulo any integer k, using d = and (e)) 2mi/ A
(())) = 1, B = 0. ho = 1. This is generalization of the construction
for PARITY described in Section B.2 since 2m1/2 1.
The of regular languages known be in TC is the set of regular languages whose syntactic monoid contains no non-solvable groups [Barrington et al. 1992]. These languages are recognized
by cascade products set-reset automata and automata perfoming modular counting [Straubing, 1994]. By the remark above, together with Lemma 9 and Lemma 20 such cascade products can be simulated by SSMs.
B.4 Maintaining Counters
As the first step in showing Theorem 5 we show that SSMs can maintain unbounded counters, and that one can read out the values of such counters, up to finite bounds, even at finite precision:
Lemma 23, Let C> 0 be an integer. Let any function u E z be given. Let L E N. Then a one-layer SSM with finite precision can compute, each position I,...T::
T:
min ( a(mm))bl -LL J=1
max
(16)
in the sense that p can read this out from 20 with finite precision.
Proof. Define d = 2L 1. Define hg = E Rd. For each x E E, define A(e,) = le and B(ex); e Rd by B(ex); = u(x). In order to read out the state h; up to a limit L, we define
((h,,,;) = Norm (0,1, 1,2, -2, -...., L1,
(17)
By testing which entries of the result are negative or positive, one can read out the state up to after rounding ((h,,,, to finite precision. The proof straightforwardly extends to multiple counters.
We are ready prove the theorem:
Theorem 24 (Restated from Theorem 5) The languages Dyck-1, Shuffle-Dyck, n-ary Boolean Ex- pressions, b". bb and e (defined in Appendix C) can each predictively modeled by an SSM.
26

---

Proof. For each of these languages, we first define an assignment u: Σ - 3+22. 2
For d²bh: (here, C=1)
u(a)= =1
u(b) = -1
For Dyck-1: (here, C=1) u(*(")
u(*)") -1
For Shuffle-Dyck-k (here, C C= k)
u(*(") (O.....,.. 1,)
where is in the i-th slot
u( u(*);") = 0,, (0,..,,,,-110....
0111,0...0)
where i-th slot
For b" (here, C=2)
u(a) = (1,0)
u(b) (-1,1)
u(c) = (0, -1)
For e"d" (here, C=3)
u(a) = (1,0,0)
(b) (,1,1,0)
u(c) = (0. 11,1)
u(d) (0.-1,-1)
For Boolean Expressions: (here, C=1)
u( ((VAILEE) =
u((n - ARY)) = +-n
For each of these mappings, use Lemma 23 at /. construct one-layer SSMs that can, for each the counters, distinguish the values - 1, 1,0,2 2 1.
In parallel, we pass the input symbol itself in log Σ further dimensions.
Overall, the output & of single SSM layer provides, at every position, both the original symbol in and an element of f 11, 100213 1)c.
string over enriched string of symbols di d2 Σ {< 1,0 C. Based on this, one can predictively model these languages as follows.
We can thus view the output of this layer
0, and "(" or ")" after any other prefix (note that For Dyck-1, the next token is EOS or "(" if predictive modeling assumes valid prefixes).
Shuffle-k-Dyde -yckk is similar: EOS is allowed if and only if all counters are zero. An opening bracket always allowed. A closing bracket only allowed if the respective counter is 0.
For a"b", the next token is a or b 6 a; if a = (a. 1) or (b, (b,2 1); EOS if a = (b,0).
Constructions for c"b"c", c" are similar.
For Boolean expressions, the token is (n ARY) EOS if 62 0, and any other token other-
wise.
All of these constructions be encoded using appropriate function applying 2..
27

---

B.5 Bounded-Dephi Dyck
Definition 25. The language D (Hewitt al. 2020 Yao et al. 2021b] is given by the CFG
with the nonterminals (S..S1..... Sn-1. 1.Sb} and the following production rules:
Sn (1S) )1
(xS)-1)x(
Sh-1 (1Sh 2)1 |||
(x:S0-2)x
82 (1S))
(xxS))xe
Si (156) (..50)))--1(xx)))r
So -
and the start symbol Sn-
Theorem 26 (Restated from Theorem 6). There is two-layer SSM with d = O(hlog that pre- dictively models Dyckk,h all input lengths, at finite precision.
Proof. In the first layer, calculate each token depth up to h using Lemma 23
After the first layer, each position, the activations will indicate both the depth up to h, and the identity of the symbol.
The space of activations is thus {0.... ./} | {(1,)....... (x. )x J. We then, for each depth / = I.....h, define a set-reset automaton (Defimition 8 given by the set Qi == {1} {(I.)...... (K. )x} Running all of these set-reset automata will tell us, for each depth, the identity of the last bracket at that depth. We can deduce the maximum depth / at which the last bracket is an opening one, and thus infer the set of valid next symbols. The activity of these set-reset automata can, in parallel, be simulated by second SSM layer using Lemma
9
We need such automata, and each SSM has width log K. 0
C Definitions of Languages
Here, we provide formal definitions of languages from the test suite based on Bhattamishra et al. (2000. Descriptions follow Bhattamishra et al.) (2020), and are included here for self seff-containment. In all cases, our data generation setup directly taken from [Bhattamishra et al. 2020
C.1 Regular Languages
Tomita Grammars. Used primarily as a benchmark language family for assessing sequence to sequence models [Tomita 1982], some of the languages in this family are star-free (with dot- of 1) and some non-star-free. All the regular languages of the family are defined on the alphabet f0, }.. Individual language definitions are available in Table
Dn- We follow the definition of BBhattamishra et al. 2020 to define the D2 family of star-free languages. In experiments, only generate D2, D3, D4, and D12 languages; D2 is equivalent to Tomita-2. All the languages of the family are defined on the alphabet of E (a, D2 (a)n- has level in the dot-depth hierarchy.
PARITY. PARITY is the set of all strings on the alphabet == {0, 13 such that the number I's is even. This language can be easily recognized by DFA with just two states.
Others. We further have the non-star-fiee languages (aa)", (aaaa)" and (abab)', and the star-free languages aa" bb" ce" dd ee", {ab}" d(b,c)', and (0, 122
C.2 Counter Languages
Dyck and Shucfle-Dyck. Dyck-1 defined on the alphabet Σ {b]} and derived using the follow- ing CFG production rule: S > SS}e.
We further
the family of Shuffle-k languages (Suzgun et al. 2019 Shuffle-Dyck-k is defined
in terms of Σ = ((.))...... (x. )-) It is defined as the shuffle of Dyck-1 languages, each defined in terms of the alphabet Σ, {(E: );) where i I,...,k.
n-ary Boolean Expressions. This is the set of valid expressions over various operators. We focus on up-to-3-ary expressions, defined using the following grammar:
28

---

S (VALUE)
(UNARY OPERATOR)
S - (BINARY OPERATOR) S
S (TERNARY OPERATOR) SSS
This language is recognized by a counter automaton Fischer et al. 1968a
Others
We further include the languages of the forms d"I,', d' and dd
Grammar
Star-Free
Definition
Yes
1
2
Yes
(10)*
3
No
strings without 12 substrings strings of even length with
4
Yes
strings without any 000's substrings
5
No
number of I's
No
strings where number of O's number I's divisible by 3
7
Yes
0* 1*0*1
Table 1: Tomita Grammars
D
Experimental Details
All experiments used the Mamba reference implementatior x Unnesss stated otherwise, we followed the defaults given there dsstate 16, deanv = 4, expand 2), found the default combination to work better than other options. We tuned dmade! for each language.
D.1 Test Suite from Bhattamishra et al. 2020
Data Preparation For all the languages, use either the data prepared by Bhattamishra et al. [020 or or-where not available- their data-generation scripts, allowing full comparabil- ity with results they reported for transformers. We used their official code and data release at http://rraanoooeeoorrooeeoo httpa/aa......aaaaaaaaaaaaaaaaaa
Languages (last commit 48eca2e; MIT license). Training sets typically consist of 10K samples, with lengths varying between to 50. There are two heldout bins: one with in-distribution lengths ([1,50), and one testing length generalization (lengths [51,100]]. The first one was used for hyperparameter optimization. Each bin typically contains around 2K samples. However for languages such as a"b", where the number of positive examples each bin was limited, all possible examples for that bin are included.
https://qithub. com/ satwik77
Hyperparameters For each language, we conducted extensive hyperparameter search. We varied the dmode parameter Mamba across the set {16, 32, 64, 128, 256) Additionally, we experimented with the number of layers in model, ranging from 3, training each configuration for 100 epochs. For languages where Mamba performed well, this number of layers was sufficient. However, for languages where Mamba struggled, increased the number of layers up 12, with little to no success.
We used the AdamW optimizer. To identify optimal learning rates, started with coarse hyper- parameter search using values from the set (0.001, 0.0001, 0.00001). }. one of these learning rates showed high performance, rate. Finally, we varied the batch size from (16, 32, 64) for datasets with 10K training examples. For languages like d² with limited training size, searched for optimal batch size within the set (5, 10).
conducted more fine-grained search to find the optimal learning
D.2 FlipFlop
We obtained the dataset of Liu 2023a from their release, https://huggingfaes co/
datasets/ synttstg/thgghseeeeeee/ee fl f 1llflooo op (MIT license). Our setup corresponds to the deterministic ("clean") mode in Liu [223a]. Matching Figure in et al. 2023a], we evaluated both with
29

---

Language
Model
Bin-1[1, 501
Bin-2[51, 100]
Bin-3[101, 150]
Transtormer
100.0
100.0
100.0
Mamba
100.0
62.6
13.91
Dyck-1
Mamba2
100.0
49.1
9.5
Mamba3
100.0
53.95
10.0
Transformer
100.0
100.0
93.0
Mambal
100.0
49.5
2.3
Shuffle-2
Mamba2
100.0
61.5
8.2
Mamba3
100.0
63.5
9.7
Transformer
100.0
100.0
98.8
Mambal
100.0
44.4
4.3
Shuffle-4
Mamba2
100.0
63.8
7.2
Mamba3
100.0
56.2
7.8
Transformer
100.0
99.9
94.0
Mambal
100.0
39.4
3.4
Shuffle-6
Mamba2
100.0
61.2
6.75
Mamba3
100.0
59.6
9.85
Transformer
100.0
100.0
99.8
Mambal
99.75
65.7
7.05
Boolean-3
Mamba2
99.95
47.25
2.3
Mamba3
100.0
73.45
8.6
Transformer
100.0
99.8
99.0
Mambal
99.9
30.05
7.6
Boolcan-5
Mamba2
100.0
80.2
14.9
Mamba3
99.25
60.7
6.25
Transformer
100.0
100.0
100.0
Mamba
100.0
4.1
d"
Mamba2
100.0
9.4
Mamba3
100.0
21.3
O
Transtormer
100.0
100.0
100.0
Mambal
100.0
0
0
c"
Mamba2
100.0
7.6
Mamba
100.0
5.1
0
Transformer
100.0
100.0
99.4
Mambal
100.0
4.76
0
dd
Mamba2
100.0
Mamba3
100.0
Table Accuracies the counter Languages from the Bhattamishra al. [2020) test suite. Trans- former results reported based on BBhattamihra et al. [2020). For Mamba, we report best settings (chosen based on inputs of length [1,50]) (Mambal 2 (Mamba2), (Mamba3) layers. Results for the best- cest-performing layer count, from the first two bins, are shown in Figure On these lan- guages, there is also a third bin.
in-distribution data (matching the distribution of the training dataset) with p: = 0.8, Pw 0.1, 0,1, and using an out of distribution sparse tail with pi = 0.98, = 0.01, = 0.01, where pi, Pw Pr refer the probabilities of that instruction appearing in input sequences.
We trained a one-layer Mamba with the default parameters setting dmodel to 16 with the AdamW optimizer using a learning rate of 3x10 and batch size of 16.
Following evaluation criteria for LSTMs in Liu et al. (2023a], we compute the test every 100 training steps on our validation sets of choice, by randomly sampling around 10 samples from each set in every evaluation cycle.
30

---

Language
Model
Bin-1[1, 50J
Bin-2[51, 100]
Transformer
100.0
100.0
Mambal
100.0
100.0
Tomita
Mamba2
100.0
100.0
Mamba3
T00.0
T00.0
Transformer
100.0
92.4
Mambal
100.0
T00.0
Tomita 4
Mamba2
100.0
100.0
Mamba3
100.0
100.0
Transformer
100.0
100.0
Mambal
100.0
100.0
Tomita
Mamba2
100.0
100.0
Mamba3
100.0
T00.0
Transformer
100.0
100.0
Mambal
100.0
100.0
Tomita 2
Mamba2
100.0
100.0
Mamba3
100.0
100.0
Transformer
100.0
100.0
Mambal
100.0
100.0
aa' bb* dd'
Mamba2
100.0
100.0
Mamba3
100.0
100.0
Transformer
100.0
100.0
Mambal
100.0
100.0
d(b.)'
Mamba2
100.0
100.0
Mamba3
100.0
100.0
Transformer
100.0
68.7
Mambal
100.0
T00.0
(0,1,2)*02
Mamba2
100.0
1O0.0
Mamba3
100.0
100.0
Transformer
74.6
3.1
Mambal
100.0
100.0
D2
Mamba2
100.0
100.0
Mamba3
100.0
100.0
Transformer
80.9
8.5
Mambal
100.0
100.0
D3
Mamba2
100.0
TO0.0
Mamba3
100.0
100.0
Transformer
90.2
3.3
Mambal
100.0
100.0
D4
Mamba2
100.0
100,0
Mamba3
100.0
100.0
Transformer
95.18
1.5
Mambal
93.65
93.35
D12
Mamba2
99.9
95.55
Mamba3
99.99
99.85
Table 3: Accuracies on the regular Languages from the Bhattamishra et al. (2020) test suite 1st half. Transformer results reported based on BBhattamishra al. [2020]. For Mamba, we report best settings (chosen based on inputs of length [1 1,500) at (Mambal) 1). (Mamba2), 3 (Mamba3) layers. Results for the best-performing layer count also shown in Figure
D.3 Bounded Hierarchical Structure
We built on the official code and data release of Yao et al. [2021b] at https:://ithhui com/ ppinceton-nip/ http:p//cccktttttsstsee prinneeco--ilp//dddtt--aaaaae
former (last commit: 5d21fef). We train a 2-layer Mamba and 1-layer Mamba on Dyckg with K = 8 and h = 10. The training set and the validation set contains samples of lengths < 700, while the test set contains samples of lengths 700 S n S 1400. We train Mamba with varying number of layers / {1,2} and dmodel E {20, 30, 40, 50, 60, 70, 80,90, 90, 100).
31

---

Language
Model
Bin-1[1, 50]
Bin-2[51, 100]
Transtormer
68.7
0
Mambal
26.95
Parity
Mamba2
80.05
4.15
Mamba3
91.15
16.7
Transformer
100.0
Mambal
2.1
(aa)*
Mamba2
2.1
0
Mamba3
4.2
Transformer
100.0
(aaaa)"
Mambal
0
Mamba2
Mamba3
4.0
0
Transformer
100.0
2.5
Mambal
0
0
(abab)"
Mamba2
Mamba3
Transformer
75.4
10.8
Mambal
25.99
12.49
Tomita 3
Mamba2
36.88
17.05
Mamba3
60.85
29.37
Transformer
29.3
0.0
Manbal
13.94
Tomita
Mamba2
34.5
0
Mamba3
38.4
Transformer
88.8
Mambal
7.2
Tomita
Mamba2
37.8
Mamba3
54.56
0.04
Table 4: Accuracies on the regular Languages from the Bhattamishra et al. [020 test suite - contin- ued. Transformer results reported based on [Bhattamishaa al. [2020). For Mamba, we report best settings (chosen based on inputs of length [1,50]) at (Mambal)) (Mamba2), 3 (Mamba3) layers. Results for the best-performing layer count are also shown in Figure
We use the Adam optimizer with an initial learning rate of 0.01 or 0.001, using cross-entropy loss. After training for 100 epochs (with early stopping allowed in case of convergence), select the learning rate with the better training performance.
E Finite Precision Assumption
As described in Section we adopt the finite precision notion used by Weiss et al. 2018): We allow an unbounded number of integer bits, but only p fractional bits, where p is sufficiently large constant (e.g., 8), independent of the length of the input.
There variety of related precision notions in the theoretical literature neural sequence models here we discuss the effect of other notions on our results:
1. Infinite precision Infinite precision allows any parameter and intermediate value to be an arbitrary number. Such setting is unrealistic, as it would allow encoding arbitrary detail about the input into infinite precision [e.g. Siegelmann [999] and read these
with sufficiently powerful functions (A, B, 6) in 4 this would lead to the unrealistic conclusion that any function and language could be represented. For this reason, theoretical work has often adopted restricted precision notions.
2. Finite inventory of values, where integer and fractional bits are both restricted. Such setup may be justified based on the fact that any real computer has bounded memory,
32

---

Mamba SSM Layer 1 vs Layer 2 (Dyck-(8. 10), Validation)
Mamba SSM Layer 1 vs Layer 2 (Dyck-(8, 10). Test)
1.0
1.0
Closs Accuracy
0.8
0.8
0.4
0.4
Model
Model
2 Layer Mamba
0.2
2 Layer Mamba
Laer Mamba
1 Layer Mamba
0.0
0.0
25
75 Memory Dimensions
50
100
25
50
75
100
Memory Dimensions
Figure 7: Mamba Accuracy on Dycky, 10. on the development (length S 700, same length range as training set) and test set (length 700 S n < 1400). The latter is also plotted in Figure 4
though such setup precludes any positive results non-finite-state problems for any computational architecture 10
Such a restrictive setup would not affect our positive results on Flip-Flop. Star-Free, and bounded-depth Dyck languages (Theorems[] 6). as these all use bounded finite-precision activation values. As this is a more restricted setup than the one we are assuming, this also would not affect our negative results about PARITY and con-star-free languages (Theo- rems 2 4). These results are thus highly robust to variations of the finite precision assump- tion.
Such more restrictive definition would, however, mean that, for unbounded counting (Theorem (5). modeling is only possible up to bound determined by the number of pos- sible values-this is the one place where our results would be impacted. Indeed, we do observe that Mamba learns these counter languages length generalization. Transformers. on the other hand, can represent these languages with bounded activations (due the constructions in Bhattamishra et al. 2020 and show strong length generalization.
training lengths but struggles with
An intermediary between infinite and finite precision is notions of precision where the number of allowed bits slowly increases with the input length, e.g., logarithmically. Such setup has particularly been adopted for transformers [Merrill and Sabharwal] [023), be- cause a finite-precision assumption leads to very low expressivity in translormers. For SSMs, on the other hand, find that finite precision assumptions sufficient for show- ing a broad range of positive results.
Foror instance, Turing machine with bounded memory and thus a bounded tape is equivalent a state automaton.
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction summarise the theoretical and empirical results. We took to only include well-supported claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The Discussion section includes paragraph on Limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specificattin, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [es]]
34

---

Justification:
Every theorem is proven formally in the appendix. Assumptions about the SSM architecture are stated formally.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the of the paper should be comple- mented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Besides describing experimental details, we have publicly released our code- base on GitHub and added link to it in the main paper with instructions on how to run our experiments, ensuring that our findings can be reproduced.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g. in the case of a large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which thors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
35

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Yes, we have publicly released our codebase on GitHub and added a link to it in the main paper with instructions how to run experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (attps://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" am acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips. Cc/ http:/uublcggddeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We have specified the training and test details in dedicated appendix section. Our experiments use freely available dataset or dataset generating scripts from previous studies, which we cite. Our uploaded code base ensures that all settings are reproducible.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [No]
Justification: In the empirical results relevant to supporting our positive theoretical results, the accuracy attained by Mamba is either very close to 100% far from 100%. As the test sets include hundreds or thousands of data points, error bars would not add substantial further information.
Guidelines:
The answer NA means that the paper does not include experiments.
36

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g,, Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of eπrоrs is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have provided information in the appendix section on experimental setup.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g.. preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We have verified compliance with the NeurlPS Code of Ethics,
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper studies foundational properties of neural network architectures, and foresee positive negative socictal impact of the results.
37

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We not releasing data models, and foresee risk of misues of our theoretical results.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The paper cites the original papers, and provides details in the Appendix section on experimental details.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
38

---

The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithoode, com/ dat has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
The paper releases no new assets.
Guidelines:
The answer means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper involves no crowdsourcing nor human subjects research.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper involves no crowdsourcing nor human subjects research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
39

---

Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
40


Reviews:
[{"review_id": "hKoQAEYKBE", "reviewer": "Reviewer_6tRo", "summary": "This study investigates the expressive power of SSMs compared to Transformers and RNNs from the perspective of formal language classes (or circuit complexities), and reports their distinct strengths. Previous studies have shown that both SSM and Transformers are in TC0, suggesting some state tracking problems are hard for both models. This study shows that both models cover overlapping but distinct parts of TC0. Theorem 1 claims that two-layer SSM can predictively model the Flip Flop (a star-free language) state tracking, and Theorem 2 claims that no SSM with non-negative gates can recognize PARITY (a non-star-free language). Since Flip-Flop and PARITY are building blocks of star-free and non-star-free languages, Theorems 1 and 2 are summarized to Theorem 4 claiming that SSMs with non-negative gates can predictively model a regular language L iff it is star-free. Further Theorems 5 and 6 claim several context-free and context-sensitive are predictively modeled by SSMs. Experimental results support theoretical claims.\n\nDue to the limitation of resources, I did not check the proofs. In particular, I am not familiar with formal language theory and I did not have enough time to learn about it. This is a __suggestion for chairs__ for future avoidance of mismatches, that the reviewers should be __examined__ if they have fundamental knowledge/background/understandings in the field. I am an expert of expressive power analysis, but not at all of formal language theory. Unfortunately, this kind of mismatch happens every year, so I am usually skeptical to any mathematical ''theorems'' published in machine learning conferences.", "questions": "- Is the assumption of non-negative gates critical in Theorem 4? If so, can Mamba be improved by replacing non-negative gates (such as ReLU or Swish) with signed gates (such as Leaky ReLU)?\n\n- Some authors claim that neural networks are Turing complete. For example,\n\n  [PMB19] _Jorge Pérez, Javier Marinković, Pablo Barceló, On the Turing Completeness of Modern Neural Network Architectures, ICLR2019_\n\n  If I understand correctly, TC0 is a subclass of regular language, and strictly smaller than Turing machine. What are essential differences from their claims?", "limitations": "n/a", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Previous studies are precisely reviewed.\n- Theorem 4 strictly refines the previous results that SSMs are in TC0, a subclass of regular languages.\n- Theorem 5 and 6 are new results in context-free and context-sensitive languages.", "weaknesses": "I am really interested in reading the manuscript. Just because I am not familiar with formal language theory, some expressions were a bit hard to parse for me. For example, \n- in Eq.4, what does the subscript of w_{1…t} mean? In the previous sentence, w does not have any subscript. Are they the same or distinguished?\n- at l.215: “L is non-star-free if and only if recognizing it involves counting modulo some K.” What is K?\n- It would improve the readability if the authors could explain what is TC0. In my opinion, NeurIPS audiences (are familiar with sample complexity but) are less familiar with computational complexity.\n- What is Chomsky–Schützenberger theorem?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments and questions. We address the raised points as follows:\n\n### Response to Weaknesses:\n\n- Equation 4 Notation: We acknowledge that the subscript $w_{1...t}$ in Equation 4 was intended to indicate that the prefix $w$ consists of a sequence of $t$ inputs, but it is superfluous. We will revise the notation for consistency and clarity, matching the representation in the previous sentence.\n- Modulo Some K: The reference to \"modulo some K\" at line 215 indicates that $K$ is a natural number ($K \\in \\mathbf{N}$). For instance, in the case of Parity, $K$ is 2 because we use modulo 2 to determine the sequence output. \n- Explanation of TC0: While TC0 is a common term in computational complexity literature, we agree that it might not be familiar to everyone in the diverse NeurIPS audience. Although space constraints prevented us from including a detailed explanation in the main paper, we will add a brief explanation in the appendix to improve readability.\n- Chomsky–Schützenberger Theorem: The Chomsky–Schützenberger theorem is a foundational result in formal language theory. It states that any context-free language can be represented using a combination of a Dyck language and a regular language. More formally, any context-free language can be expressed as a homomorphic image of the intersection of a Dyck language with a regular language.\n\n### Response to Questions:\n\n> Is the assumption of non-negative gates critical in Theorem 4? If so, can Mamba be improved by replacing non-negative gates (such as ReLU or Swish) with signed gates (such as Leaky ReLU)?\n \n- Our proof for Theorem 4 does make the assumption of non-negative gates. With more general gates, we show in Theorem 21 (page 22 in the Appendix) that expressiveness would increase substantially.  In Mamba, the non-negativity is created by parameterizing gates as exponentials. We have attempted to change the implementation to allow signed gates, but found training to stop working, suggesting the non-negativity may be useful for training. We believe that studying SSMs without the nonnegativity constraint presents an interesting oppportunity for follow-up work.\n \n> Some authors claim that neural networks are Turing complete. For example, [...] If I understand correctly, TC0 is a subclass of regular language, and strictly smaller than Turing machine. What are essential differences from their claims?\n\n- Regarding the Pérez et al. paper, it is indeed a seminal piece of work, and we do cite it in our paper. Its results show the Turing completeness of transformers when they are allowed to generate an unbounded number of intermediate tokens before making their decision -- akin to chain-of-thought and scratchpad techniques. This is a key difference to our setup: We are interested in the expressiveness of neural models when they have to make their decision immediately upon processing the input, without additional intermediate steps. This is foundational because any additional steps would result in higher computational cost. Indeed, there is work [1][2] showing that transformers become more expressive than TC0 when allowed intermediate steps (while increasing computational cost due to intermediate steps) -- and we believe that the same arguments will hold for SSMs.\n\n[1] Li et al, Chain of Thought Empowers Transformers to Solve Inherently Serial Problems, ICLR 2024\n\n[2] Feng et al, Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective, NeurIPS 2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ojYb96B3EL", "reviewer": "Reviewer_tByQ", "summary": "This paper presents a comprehensive theoretical and empirical analysis of the expressive capacity of modern State Space Models (SSMs) within the framework of formal languages and automata theory. The authors establish important theoretical results, demonstrating that SSMs can effectively model star-free languages, various counter languages, and bounded hierarchical structures without relying on explicit stack mechanisms. By leveraging the Krohn-Rhodes theorem and concepts from algebraic theory, the paper provides rigorous proofs showing the capabilities and limitations of SSMs in capturing different language classes. By connecting theoretical computer science (TCS) with machine learning (ML), the paper highlights the importance of understanding the fundamental limitations and capabilities of computational models.", "questions": "- While the experiments on synthetic datasets and formal languages are comprehensive, additional experiments on more complex and diverse real-world tasks could strengthen the empirical validation. Are there any plans to extend the experimental validation to other types of datasets or applications that are not necessarily big, but challenging and prove the points?\n- The paper briefly mentions the practical implications of the theoretical insights for designing new ML architectures. Could the authors provide concrete examples or guidelines on how to implement these insights in real-world systems? What are the key considerations for practitioners looking to apply these findings?", "limitations": "Already addressed by authors.", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- The paper introduces a novel theoretical framework that connects formal language theory with the expressive capabilities of State Space Models (SSMs), a relatively unexplored area in machine learning research.\n- By leveraging the Krohn-Rhodes theorem and algebraic theory, the authors provide proofs and characterizations of the language classes that SSMs can model, including star-free languages and bounded hierarchical structures.\n- The integration of TCS concepts with modern SSM architectures is important because through TCS we study the limits and what is possible or not possible\n- Theoretical contributions are rigorously presented, with clear and detailed proofs supporting the claims about the expressive power of SSMs. I checked all the proofs thoroughly and I am sure they are valid.", "weaknesses": "- While the paper does an admirable job of explaining complex theoretical concepts, some sections may still be challenging for readers without a strong background in theorem proving. Additional intuitive explanations or visual aids could help make the content more accessible.\n- In the related work section add more works that study this, in particular: Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory. Nikola Zubić, Federico Soldá, Aurelio Sulser, Davide Scaramuzza - https://arxiv.org/abs/2405.16674 . Mention also how does your work overlap with it and is there any interesting connection?\n- There are typos, use for example Grammarly to fix them. Also there are some typos in math, for example Lemma 22 should have w_j inside the sum, not w_i etc. Check and make sure indexes are well defined. Theorems are proven well, but there are typos.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their high score and positive comments about our paper. We appreciate the reviewer's thorough examination of our proofs and their constructive insights and suggestions. We address the points raised as follows:\n\n### Response to Weaknesses:\n\n> While the paper does an admirable job of explaining complex theoretical concepts, some sections may still be challenging for readers without a strong background in theorem proving. Additional intuitive explanations or visual aids could help make the content more accessible. \n-  We acknowledge that some sections of the paper may be challenging for readers without a strong background in theorem proving. To make the content more accessible, we will include additional intuitive explanations and visual aids. Specifically, we will add visual representations to help elucidate the SSM constructions described in our theorems.\n\n> In the related work section add more works that study this, in particular: Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory. Nikola Zubić, Federico Soldá, Aurelio Sulser, Davide Scaramuzza - https://arxiv.org/abs/2405.16674 . Mention also how does your work overlap with it and is there any interesting connection?\n\n- The paper by Zubić et al. indeed represents significant work in the field of analyzing expressivity of SSMs. Their approach differs from ours in that they focus on a range of algorithmic tasks, such as function composition, whereas we focus on fine-grained study of length-generalizable expressions for core formal languages. We do not see any overlap in results, but will make sure to include the comparison in the related work section of our main paper.\n \n  \n> There are typos, use for example Grammarly to fix them. Also there are some typos in math, for example Lemma 22 should have w_j inside the sum, not w_i etc. Check and make sure indexes are well defined. Theorems are proven well, but there are typos.\n\nWe apologize for the typographical errors and mistakes in the mathematical notation, such as the incorrect index in Lemma 22. We will thoroughly proofread the paper  again and carefully correct all the typos we missed. \n\n\n### Response to Questions: \n> While the experiments on synthetic datasets and formal languages are comprehensive, additional experiments on more complex and diverse real-world tasks could strengthen the empirical validation. Are there any plans to extend the experimental validation to other types of datasets or applications that are not necessarily big, but challenging and prove the points?\n- We agree that additional experiments on more complex and diverse real-world tasks would further strengthen our empirical validation, and we do plan to do the same in follow up work. \n\n> The paper briefly mentions the practical implications of the theoretical insights for designing new ML architectures. Could the authors provide concrete examples or guidelines on how to implement these insights in real-world systems? What are the key considerations for practitioners looking to apply these findings?\n- One of the main practical implications that can be taken from the theoretical insights of our paper in designing new ML architectures is for future architectures to combine the strengths of attention with that of the SSM recurrence update, and indeed some work [1][2][3] that has been published since our submission has found empirical evidence of the same. We do agree that more concrete examples and guidelines could be given and would include some examples in the appendix of our paper due to space considerations. \n    - [1] Lieber, Opher, et al. \"Jamba: A hybrid transformer-mamba language model.\" arXiv preprint arXiv:2403.19887 (2024).\n    - [2] Waleffe, Roger, et al. \"An Empirical Study of Mamba-based Language Models.\" arXiv preprint arXiv:2406.07887 (2024).\n    - [3] Ren, Liliang, et al. \"Samba: Simple Hybrid State Space Models for Efficient Unlimited Context Language Modeling.\" arXiv preprint arXiv:2406.07522 (2024).\n\nWe once again appreciate the reviewer’s positive comments and valuable feedback and will incorporate the suggestions to enhance the clarity, completeness, and practical relevance of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KlKvKm2Ymy", "reviewer": "Reviewer_9mjL", "summary": "The paper presents several results on the expressiveness of *state space models (SSMs)*, viewed as *language acceptors* or a weak form of *language predictors*, from the perspective of formal language theory. These results are parametrized to subsume currently common SSM architectures, including *non-negative SSMs*, which encode prefixes using positive reals only, *time-invariant SSMs*, where prefixes are encoded independent of the currently considered token, and *finite precision SSMs*, meaning that internal computations are limited by a fixed number of fractional bits.\n\nIn more detail, the paper presents the following results:\n- The FlipFlop language is predicted by a two-layer SSM with finite precision (Theorem 1), and there is no non-negative, finite precision SSM that recognizes the PARITY language (Theorem 2).\n- The class of non-negative, finite precision SSMs predicts exactly the star-free languages (Theorem 4).\n- Various kinds of languages that require unbounded counting, such as Dyck languages, $a^nb^nc^n$, or boolean expressions, are predicted by an SSM.\n\nIn summary, the paper establishes foundational results categorizing the expressive power of SSMs within the well-established framework of formal language theory. Additionally, this allows for a comparison of SSM with their imminent competitor, transformers, for which similar architectures exist. This comparison is empirically supported by experiments.", "questions": "- The notion of finite precision you are using seems to have been considered before. Could you elaborate on why it is a reasonable one? \nAt first sight, it seems artificial, as you either consider practical settings where you are limited by some amount of bits for representing a number, or you do not care for practical realizations and thus everything can be unbounded. The notion you used feels a bit like a convenience choice, as fixing fractional parts helps keeping fuzziness under control but still allows for unbounded counting using unbounded integer parts. Especially, in the context of your positive, predictive results regarding finite precision. I assume these do not hold for an overall bounded number of bits.", "limitations": "The authors state the limitations of their work, mainly focusing on the lack of experimental evaluation, which is sufficient regarding this part. However, I would have appreciated a clearer statement on open questions focusing on the theoretical contributions. For example, they could discuss related work on other models like RNNs or Transformers and which results about formal language recognition or prediction exist in those contexts, which have not yet been considered in the context of SSMs.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The paper considers the expressiveness of recent SSMs from the perspective of formal language theory. While it is not new to analyze sequence-classifying or sequence-to-sequence models from a formal language viewpoint, this paper is one of the first to do so for SSMs on a broad scale. Additionally, this is a reasonable continuation of preceding work, particularly for understanding the differences in expressiveness between SSMs and transformers.\n\nThe main result, at least from my perspective, Theorem 4, states that SSMs predict exactly the star-free languages. This is fundamental, making it well worth considering. The remaining results are more specialized, focusing on particular languages. However, these also provide insights for a more detailed understanding of the expressive power of SSMs, especially compared to transformer. Thus, these are of clear relevance as well.\n\nIn general, all results are supported by technical proofs and some intuition building, allowing the reader to verify the soundness of the results in sufficient detail without unreasonably extensive effort.", "weaknesses": "The clarity and quality of the paper could be improved. This is mainly due to three reasons:\n- This first reason is minor compared to the others. There are many results in this paper, which is desirable. However, it is a bit difficult to get an overview of the results. For example, it is unclear which should be considered the main result. Of course, it could be the case that there is not a single main result, which I assume applies here. However, the structure of the results seems odd, as we first show what is (not) possible for some languages (Theorem 1, Theorem 2), then consider a general result (Theorem 4), and then, again, focus on specific languages (Theorem 5 and Theorem 6). I think the main problem is that all results are squashed into a single “Theoretical Results” section, which is also mixed with basic definitions like finite-state automata and (star-free) regular languages. Giving the reader a better hint on the central theme of the results and a clear separation of preliminaries and results would improve the clarity of the paper.\n\n- The authors tend to state lemmas and theorems informally, making it hard to grasp the concrete setting. For example, Theorem 2 states, *”… can recognize PARITY at arbitrary input lengths …”*. It is not precisely clear what this means, especially the “arbitrary length” part. Or take Lemma 13 in Appendix B.3. This lemma states that *”… the character $w_{t-1}$ can be read out from $z_t$ at finite precision.”*. It is hard to understand what is exactly meant by this, too. The same goes for the overall statement of Lemma 22. \nWhile I appreciate that the main part of the paper focuses on a low-technical presentation, such a theoretical work cannot be separated from its technical appendix. Therefore, statements in the appendix should be precise. This goes beyond these three examples and is a general problem. This also applies to the exact SSM architecture considered in respective results. In most cases, one can guess what is meant, but I don’t think such things should be left to the reader’s imagination to this degree.\n\n- Some proofs could be more detailed. For example, the proof of Lemma 17 includes previously unused notation (line 824, $w_{1..t} = …00$), it is not clear how equalities (15) and (16) are derived or what *”… running these in parallel, …”* means.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive score and encouraging review. Regarding the issues pointed out:\n\n### Response to Weaknesses:\n\n> This first reason is minor compared to the others. There are many results in this paper, which is desirable. However, it is a bit difficult to get an overview of the results. For example, it is unclear which should be considered the main result. Of course, it could be the case that there is not a single main result, which I assume applies here. However, the structure of the results seems odd, as we first show what is (not) possible for some languages (Theorem 1, Theorem 2), then consider a general result (Theorem 4), and then, again, focus on specific languages (Theorem 5 and Theorem 6). I think the main problem is that all results are squashed into a single “Theoretical Results” section, which is also mixed with basic definitions like finite-state automata and (star-free) regular languages. Giving the reader a better hint on the central theme of the results and a clear separation of preliminaries and results would improve the clarity of the paper.\n \n- The paper indeed does not have a single main result; rather, we have four major results that we aimed to make explicit and contextualize in the Take-Aways section on Page 9. We acknowledge that combining some of the background information with our main results in the Theoretical Results section was not ideal. We will separate the background information from the results into distinct sections to improve clarity.\n\n\n> The authors tend to state lemmas and theorems informally, making it hard to grasp the concrete setting. For example, Theorem 2 states, ”… can recognize PARITY at arbitrary input lengths …”. It is not precisely clear what this means, especially the “arbitrary length” part. Or take Lemma 13 in Appendix B.3. This lemma states that ”… the character can be read out from at finite precision.”. It is hard to understand what is exactly meant by this, too. The same goes for the overall statement of Lemma 22. While I appreciate that the main part of the paper focuses on a low-technical presentation, such a theoretical work cannot be separated from its technical appendix. Therefore, statements in the appendix should be precise. This goes beyond these three examples and is a general problem. This also applies to the exact SSM architecture considered in respective results. In most cases, one can guess what is meant, but I don’t think such things should be left to the reader’s imagination to this degree.\n\n > Some proofs could be more detailed. For example, the proof of Lemma 17 includes previously unused notation (line 824, ), it is not clear how equalities (15) and (16) are derived or what ”… running these in parallel, …” means.\n\n- We agree that understanding the concrete settings of our results might require the reader to refer to the appendix. We appreciate that the reviewer acknowledges our focus on intuition in the main paper, leaving technical details in the appendix. We also thank the reviewer for pointing out that some of our proofs, although correct, might require more detail. For each theorem or lemma, we will provide a fully formally precise statement in the Appendix. We will revisit all proofs and provide additional steps to better elucidate them.\n \n\n\n \n### Response to Questions:\n\n> The notion of finite precision you are using seems to have been considered before. Could you elaborate on why it is a reasonable one? At first sight, it seems artificial, as you either consider practical settings where you are limited by some amount of bits for representing a number, or you do not care for practical realizations and thus everything can be unbounded. The notion you used feels a bit like a convenience choice, as fixing fractional parts helps keeping fuzziness under control but still allows for unbounded counting using unbounded integer parts. Especially, in the context of your positive, predictive results regarding finite precision. I assume these do not hold for an overall bounded number of bits.\n\n\nWe understand that our choice of finite precision for representing fractional components versus allowing unbounded counting, and thus unbounded integer values, might seem like a convenience choice. However, we would like to clarify that we do not consider unbounded integer values in any of our theorems except for the unbounded counting case: All our results except for the unbounded counting case in fact have overall bounded numbers of bits. For unbounded counting, the task definition requires unbounded integer values, and any length-generalizing recurrent solution will require an unbounded overall number of bits. While, theoretically, a solution for unbounded counting can be constructed with SSMs, as shown in our paper, it might be unlikely that such a solution would be practical owing to such requirements of unbounded overall number of bits. Indeed, in our experiments across all counter languages in Figure 3, we were unable to get the SSM to learn a length-generalizable solution. We will expand our discussion of the precision assumptions and their implications in Appendix E, and add appropriate notes in the main paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JfW65vEx57", "reviewer": "Reviewer_px5T", "summary": "1. This paper studies the expressive capacity of state-space models from a formal language perspective. \n2. It shows that for flip-flop, SSM can do well. And for parity, SSM cannot do well.", "questions": "1. I understand the notion of finite precision assumption is necessary in practice. However, a natural question is whether increasing the number of fractional bits p can be a effective method to reduce the problem proposed in this paper. As the cost of increasing p is still linear. \n2. In the same argument, it seems transformer and temporal convolution, in the setting of convolution, also have the same problems as Theorem 2. I tend to believe this issue comes from the setup of finite precision and infinite sequence length. Any insight about this issue?", "limitations": "1. The result derived in this paper is limited to formal languages. It is not clear what is the generalization to natural languages.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. State-space models have the advantage of low inference cost, therefore using it to learn language models and formal languages are important research directions. \n2. The perspective of formal language and the proof is interesting", "weaknesses": "1. The theorem 2 seems to be problematic:\n\t1. Given sequence $\\mathbf{x} = x_1, \\dots, x_T$, consider function $f(\\mathbf{x}) = (e^{i \\pi \\sum_{i=1}^n x_i} + 1)/2$. This continuous function can achieve the goal that if $\\sum_{i=1}^n x_i$ is even, then the result is 1, otherwise the result is 0. \n\t2. Based on a cumulative sum layer, it only requires the approximation using two-layer state-space models for a function $f(x) = (e^{i \\pi x} + 1) / 2$ . There are various universal approximation theorem to prove this:\n\t\t1. https://openreview.net/forum?id=i0OmcF14Kf\n\t\t2. https://arxiv.org/abs/2307.11888\n\t\t3. They are also related works in the expressive sense.\n\t\t4. Still it is possible to have the unboundedness issue from $\\sum_{i=1}^n x_i$. \n\t\t5. I understand the notion of finite precision assumption is necessary in practice. However, another question is whether increasing the number of fractional bits p can be a effective method to reduce the problem proposed in this paper. As the cost of increasing p is still linear.  (And increasing p can relax the unboundedness issue in $\\sum_{i=1}^n x_i$ in an exponential sense. \n\t\t6. I am willing to raise the score if this issue can be better discussed. \n\t3. The experiments for 28 seem to justify that three layer mamba can work with certain accuracy. A natural question would be whether increasing the hidden dimension and layers improves the performance. \n2. The role of parameterization discussed in page 3 seems a bit lacking of related work\n\t1. HIPPO(https://arxiv.org/abs/2008.07669), Approximate Diagonalization(https://arxiv.org/abs/2310.01698), StableSSM(https://arxiv.org/abs/2311.14495).\n3. Line 682, typo - have shown.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's detailed feedback and constructive criticism. We would like to clarify/address the issues raised as follows:\n\n### Weakness\n**(1.1), (1.2)** We thank the reviewer for the interesting construction for PARITY, and the universal approximation references.\n\n  We would like to clarify why the suggested construction isn't a contradiction to Theorem 2. One could implement the suggested construction in an SSM-like architecture.  However, computing the function $f(x) = (e^{i \\pi x}+1)/2$ requires a layer-wise nonlinear function (eg an MLP) implementing sine/cosine functions at arbitrarily large inputs. Importantly, to obtain a construction working for all input lengths (as our positive results do), a single such operation would need to work at arbitrarily large input numbers.\n\nAs stated in line 56, our analysis assumes the layer-wise operations to be linear or (Swi)GLU (line 56) (as these are used in the real-world SSMs we surveyed in Appendix A). This is relevant to the proof of Theorem 2. A single GLU or SwiGLU is likely not able to represent sine/cosine for unboundedly large inputs, and we believe the same holds for more classical MLPs (ReLU/sigmoid MLPs). This is because, to the extent we are aware, universal approximation results for feedforward networks guarantee approximation in the sense of compact convergence [1], uniformly on the compactification of $\\mathbb{R}$, [2], or in $L^p$ [3], none of which cover uniform approximation of sine/cosine on $\\mathbb{R}$.  Indeed, very recently, [4] studied universal approximation in $C_b(\\mathbb{R})$, exactly what would be needed for approximating sine/cosine at any input magnitude. We believe their Proposition 5.5 entails that sine/cosine cannot be uniformly approximated with certain activation functions.\n\nThus it's not to be expected that $f(x) = (e^{i \\pi x}+1)/2$ would be implemented by a typical MLP uniformly for arbitrarily large inputs. Hence, we believe any implementation of the proposed construction would either require custom (e.g., periodic) activation functions or require model size to vary with the input length, both resolving an apparent contradiction with Theorem 2.\n\nThanks further for linking the references on universal approximation, which we will cite and discuss in the Related Work section. \n \nWe would like to clarify again, there's no contradiction of our negative result in Theorem 2 to these universal approximation results. Both Wang et al and Orvieto et al provide universal approximation guarantees, but importantly, the size of the approximating networks depends on input length. One can see this from the statements of the core formal results, Propositions 3.6 and 3.9, in Wang et al. It is clearly stated by Orvieto et al in their Remark 2. In contrast, our results (both positive and negative) concern the existence of a *single* SSM recognizing a formal language at *any input length*.\n\n  Overall, we thank the reviewer again for raising these interesting points. We will address them as follows:\n\n  (1) Cite and discuss Wang et al and Orvieto et al results.\n\n  (2) Make more salient, & mention in the Theorem 2 statement that it relies on properties of the activation functions as stated in line 56.\n\n  (3) Discuss the question whether SSMs could benefit from more general, e.g., periodic activation functions in the nonlinearities.\n \n We thank the reviewer for this insightful observation and for helping improve our paper with such constructive criticism.\n \n**(1.3)** For languages where Mamba failed to predictively model perfectly with 3 layers, we did increase number of layers to 12 and hidden dimension to 256, as documented in Appendix Section D.1. Across the languages tested, we obtained no further benefits beyond 3 layers.\n\n**(2)** In the \"Role of Parameterization\" section, we aimed to delineate the scope of our work and point out that our results aren't primarily affected by technical details regarding parameterization, as we allowed each of A, B, and $\\rho$ to be arbitrary functions. However, we acknowledge the importance of citing relevant papers that focus on parameterization and will make our point about our results being unaffected by parameterization details more explicit.\n\n**(3)** We thank the reviewer for pointing out the typo. We'll fix it.\n\n### Questions \n\n**(1)** We agree that the question of precision is interesting. Increasing $p$ to any finite bound might improve expressiveness on short inputs, but not mitigate limitations on unboundedly long inputs. An open question is to what extent increasing $p$ with input length ($N$), e.g., $\\log N$ could mitigate expressiveness limitations in theory. We will add discussion of the same.\n\n**(2)** Indeed, both transformers and convolutional networks face similar challenges as SSMs regarding PARITY. For transformers, [5] shows that such limitations *provably* persist even with infinite precision (PARITY creates very sharp minima on long inputs). We conjecture that this reflects a general phenomenon in highly parallellizable architectures, and that similar phenomena may apply with SSMs even with infinite precision.\n\n### Limitations\nWe acknowledge that our results are derived for formal languages. However, Dyck, Flip-Flop, $a^nb^n$ etc. have linguistic motivations and provide insights into the structure/processing of natural language, which we'll expand on in the camera ready version.\n\n### References\n[1] Cybenko, G. (1989). Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems\n\n[2] Ito, Y. (1992). Approximation of continuous functions on Rd by linear combinations of shifted rotations of a sigmoid function with and without scaling. Neural Networks\n\n[3] Arora, et al (2018) \"Understanding Deep Neural Networks with Rectified Linear Units.\" ICLR\n\n[4] van Nuland, T. D. (2024). Noncompact uniform universal approximation. Neural Networks\n\n[5] Hahn and Rofin (2024). Why are Sensitive Functions Hard for Transformers? ACL", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We appreciate the reviewers' detailed feedback and constructive criticism. We are particularly encouraged by Reviewer tByQ's thorough verification of our proofs and confirmation of their validity. We also recognize the valuable input from all reviewers regarding typographical errors and structural improvements to enhance the clarity of the paper. Below, we summarize the common points raised and outline our planned revisions.

We acknowledge the need for improved readability and structure in the results section. To address this, we will separate the background information from the theoretical results section, providing a clearer overview as suggested by Reviewer 9mjL. This restructuring will help highlight the four major results explicitly, as outlined in the "Takeaways" section on Page 9. Additionally, we will revise the notation in Equation 4 to ensure consistency throughout the paper.

Several reviewers pointed out the need for clearer explanations of specific concepts. We will add brief explanations of terms like TC0 and the Chomsky-Schützenberger theorem to the appendix to enhance readability for the diverse NeurIPS audience, as suggested by Reviewer 6tR0. Furthermore, in response to Reviewer tByQ's suggestion, we will include visual aids to better elucidate our proofs, complementing the theoretical details with intuitive images to help convey the core ideas of the paper.

We are particularly grateful to Reviewer px5T for suggesting a construction for PARITY. As we described in our response, this construction would not be length-generalizable -- thus resolving an apparent contradiction with Theorem 2. We will include a more detailed discussion in our camera-ready version, and thank Reviewer px5T for this insightful contribution.

We also appreciate the suggestions from Reviewers px5T and tByQ to cite additional relevant papers. We will incorporate these references into our related work section, providing a more comprehensive view of the ongoing research on the expressivity of State Space models.

Regarding concerns about our assumption of the finite precision setting, we have addressed each individual query in our responses. We are happy to clarify further if there are any additional questions on this topic.

In summary, we are grateful for the reviewers' valuable insights, which have significantly contributed to improving our work. We believe these revisions will enhance the quality and clarity of our paper, and we look forward to presenting the final version.

Meta-review: Paper provides a novel and an intriguing theoretical analysis of the expressive capacity of SSMs, a timely and relevant topic given the recent success of SSMs in language modeling. The authors meticulously connect SSM capabilities to formal language theory, offering valuable insights into the strengths and limitations of these models.

While this paper's rigorous theoretical analysis of SSM through the lenses of formal language theory and its intriguing insights into the model's capabilities are highly valuable, the following weaknesses should be addressed to broaden its impact and reach a larger audience within the community: improving the clarity and accessibility of certain sections (reviwers initially found some sections challenging to parse), particularly for readers without a strong background in formal language theory, and expanding the empirical validation beyond synthetic datasets to include more complex and diverse real-world tasks. 

The authors have committed to improving the acessibility by adding intuitive explanations, visual aids, and clarifying technical details in the appendix, and we expect these commitments to be fulfilled.
Decision: Accept (poster)