The Expressive Capacity of State Space Models: A Formal Language Perspective

Authors: yash  sarrof
yana  veitsman
michael  hahn
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:35:42

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.

Main paper: 
 introduction: 
 Transformers [Vaswani et 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 Schmidhuber, 1997 ]. However, building on a long history of continuous dynamical models [e.g. Kalman, 1960 Kalman, , 1963] ] and work on faster RNNs [Bradbury et al., 2016 , Lei et al., 2018] , a recent line of work has developed state space models (SSMs) rivaling the performance of transformers [e.g. Gu et al., 2021 , Gu and Dao, 2023 , Sun et al., 2023 , De et al., 2024 , Yang et al., 2024 , Qin et al., 2024a] . 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 is 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, a sizeable literature has studied transformers [e.g. Pérez et al., 2019 , Hahn, 2020 , Bhattamishra et al., 2020 , Yao et al., 2021a , Liu et al., 2023b ,a, Deletang et al., 2022 , Strobl et al., 2024 , Chiang et 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 et al., 2018 , Hewitt et al., 2020] through this lens. As the difficulty 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 an initial step, Merrill et al. [2024] showed that all problems computable by SSMs are contained in TC 0 , 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. Jelassi et al. [2024] and Bhattamishra et al. [2024] provided evidence of differences between these architectures, showing that transformers outperform SSMs on copying or retrieving from long strings-tasks well within TC 0 . 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-digit multiplication.However, a more fine-grained understanding of the power of SSMs, and how they compare to 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 0 . For instance, SSMs can model bounded hierarchical structure in ways similar to 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 1). We discuss take-aways for SSM and LLM research in Section 5; among others, our results suggest future LM architectures might need to combine both attention and state spaces. 
background: 
 2.1 State Space Models SSM Layers We define a single layer of a state space model as a map, at input length T , R T ×d → R T ×d (x t ) t=1,...,T → (z t ) t=1,...,Tgiven by the recurrenceEQUATIONwhere • denotes elementwise product, and, for each x t ∈ R d ,h 0 ∈R d B(x t ) ∈ R d (increment) A(x t ) ∈R d (gate) φ : R 2d → R d (transform)We allow A, B to be arbitrary smooth maps. The map φ(h t , x t ) includes a cascade of channel-mixing transformations and normalization, which we abstract as follows:EQUATIONwhere Mix j (•) can contain linear or (Swi)GLU components [e.g. Qin et al., 2024a, Gu and Dao, 2023] . We will take Norm to implement RMSNorm Zhang and Sennrich [2019] ; LayerNorm Ba et al. [2016] can be covered by absorbing centering into Mix 2 .A Full SSM Real-world SSMs typically stack several layers of the form (1-2). Where needed, we use superscripts to indicate the layers in an SSM: h(1) t , . . . , h(L)t , where L is the number of layers. We consider input words w = w 1...|w| over a discrete alphabet Σ, and assume an encoding in terms of token embeddings e(σ) ∈ R d , for σ ∈ Σ. We will also write e σ for e(σ). These feed into the lowest layer as x(1) t := e(w t ). The outputs of each layer feed into the next layer, as x(l+1) t = z (l)t . The transformations in (1) are specific to each layer: A (1) , . . . , A (L) and similarly for B, φ. To keep notation simple, we will only show the superscripts where necessary for disambiguation. The activations z (L) t at the highest layer are read out by some neural network ρ into vectors q t ∈ R d pred describing classification or next-token predictions. We again take ρ to be an arbitrary function; importantly, all our constructions will allow ρ to operate correctly even at finite precision.Implementation Choices In Mamba, (1) directly maps onto Eqs. (2a) and (2b) in Gu and Dao [2023] . The notation of Gu and Dao [2023] use a matrix multiplication Ah t-1 instead of elementwise multiplication A(x t )•h t-1 in (1), but importantly, Mamba's A is diagonal, so we can take A(x t ) i = A ii . Some SSMs assume nondiagonal A(x t ), but typically this matrix is diagonalizable [e.g. Gu et al., 2021 , Sun et al., 2023] , so that the SSM is still equivalent to one of the form (1). We discuss how other SSMs instantiate (1) in Appendix A. Some models assume complex-valued 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 x t and h t using state expansion; as this does not affect expressive capacity, we will simply assume a 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 19).We will find that two design choices have nontrivial impact on expressive capacity: The first one is time invariance: we call an SSM TIME-INVARIANT if A(x t ) does not depend on x t . Some SSMs, such as S4 [Gu et al., 2021] 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 et al., 2024b,a] , QRNN/SRU Bradbury et al. [2016] , Lei et al. [2018] are not (Appendix A). The second one is the sign of the entries of A(x t ): Across all non-time-invariant SSMs surveyed, we find that the gate is always nonnegative (Appendix A): A(x t ) ≥ 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-2) is common across the SSM literature, differences in parameterization may have substantial effect on efficiency and training stability. In particular, the parameterization of A(x t ) has been the subject of substantial research [e.g. Gu et al., 2020 , 2021 , 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, B, ρ to be arbitrary functions with the given input-output properties. Our negative results are based on abstract properties of the setup (1-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 a recent SSM [Mamba, Gu and Dao, 2023] .We contrast SSMs with traditional RNNs such as simple RNNs or LSTMs: for these, the recurrence in Eq. ( 1) is replaced by h t = ψ(h t-1 , x t ) where ψ could be linear, an MLP [Elman, 1990] , or a more complex gated function [Hochreiter and Schmidhuber, 1997] .Finite Precision Assumption While Eq.( 1) 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 p fractional bits, independent of the length of the input. See Appendix E for discussion.We study three foundational types of data structures needed for modeling formal languages [Hopcroft et al., 2001] : finite state automata (Theorem 1, 2, 4), counters (Theorem 5), and stacks (Theorem 6). These data structures can be understood in two equivalent forms: One is to track a 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 formal languages-sets of finite strings that are defined by the property that an automaton reaches one of a 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 finite-state-automaton (see Definition 7) represents a general state tracking problem over a 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 a 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 a formal language is determined by the state reached after reading the full string. Finite-state-automata are equivalent in expressivity to regular expressions, and define the regular languages [Kleene, 1951] .Figure 1 : Three key formal languages: prefixes with the sets of possible next characters: Flip Flop (Theorem 1), PARITY (Theorem 2), bounded-depth Dyck (Theorem 6). In Flip Flop, after a r (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 can 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 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 a highly structured manner. SSMs can model this datastructure (Theorem 5), as can RNNs and transformers [Weiss et al., 2018 , Bhattamishra et al., 2020] . Stacks, a first-in-first-out datastructure, enable automata to 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 a stack (Theorem 6) -these are likely to be most useful to natural language given the boundedness of human memory [Miller, 1963 , Karlsson, 2007] .We fix a finite alphabet Σ. Its elements are called characters or symbols. The set of all finite strings w over Σ is denoted Σ * ; such strings are often referred to as words. The length of w is denoted |w|. A formal language L is a subset of Σ * . Techically, we assume that the alphabet includes BOS and EOS symbols, which occurs at the beginning and end of each element of L and nowhere else.We next need to define what it means for an SSM to model a 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 d pred = 1, we say that it recognizes a language L if the output ρ(z(L)|w| ) equals-when the SSM is run on w ∈ Σ * -1 if w ∈ L and 0 else. However, such a classification task is arguably not always matched to dominant use cases in predictive sequence modeling, where the task is to predict the next token at each step. Thus, we also cast formal languages into a 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(L) := {w : w ∈ Σ * , wΣ * ∩ L ̸ = / 0} the set of valid prefixes of L. We then say that a model predictively models a language L if (Figure 1 ), given a valid prefix w ∈ Prefix(L), it outputs the finite setEQUATIONWe think of each such set as an atomic label; the set of possible labels is the power set of the finite alphabet Σ (here, d pred = 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 be done by adding 1 SSM layer. Conversely, if we can show that SSMs cannot recognize a 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. 3 Theoretical Results 
length-generalizing representations for flip-flop state tracking: 
 Flip Flop languages [Liu et al., 2023a] are a simple instance of state tracking defined in terms of write, read, and ignore instructions. Each write instruction comes with a piece of information; whenever a read instruction is encountered, the information written by the last write instruction is recalled. Formally, L FF is the set of finite strings x over Σ = {r, w, i, 0, 1}, wherex 1 , x 3 , • • • ∈ {r, w, i}, x 2 , x 4 , • • • ∈ {0, 1}, and where the bit following any r matches the bit following the last preceding occurrence of w. Liu et al. [2023b] show that the Flip Flop language, as an abstraction, is a fundamental ingredient of many long-range reasoning settings. It can be represented with a small finite-state-automaton, and LSTMs learn L FF well [Liu et al., 2023a] . Transformers can in principle represent it [Liu et al., 2023b,a] , though known constructions are not inherently lengthgeneralizing, a fact confirmed 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:Theorem 1. There is a two-layer SSM that predictively models L FF at all lengths, at finite precision.In the construction (Figure 3 ), the first layer records the last instruction token, achieved in (1) by setting A(e(r)) = A(e(w)) = A(e(i)) = 0, and A(e(0) = A(e(1)) = 1, and setting B(e(0)) = B(e(1)) = 0. Additional dimensions forward the current token to h(1)t . In the output of the first layer z(1)t , whenever the input is 0 or 1, the model now has access both to the current token w t and the preceding token w t-1 , which must have been an instruction. Based on this information, the model can set the gate to overwrite the state h(2) t-1 with the current input token when the preceding token was w, and pass along the state h(2) t-1 unaltered otherwise. This, together with z (1) t , is sufficient for always identifying the legal next symbols in L FF . The formal proof is in Appendix B.1.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., 2020 , Deletang et al., 2022] , as it can provably only be represented in sharp minima [Hahn and Rofin, 2024] . A sufficiently general SSM could easily recognize it at d = 1 by setting h 0 = 1, A(e 1 ) = -1, A(e 0 ) = 0, B ≡ 0, so that the sign of the single entry of h t indicates the parity (Figure 2 ). Such an SSM would need to be nontime-invariant and require negative or complex gate values; i.e., satisfy neither TIME-INVARIANT 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 6):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-automata, establishing an even stronger separation between existing SSM variants and traditional RNNs than the circuit complexity arguments in Merrill et al. [2024] 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 1 N and shows that the activations z N converge as N → ∞, and thus cannot reliably encode the parity of N. It should be noted that we require the layer-wise operations used in the SSM to be either linear or based on the GLU or SwiGLU activation functions, as seen for instance in Mamba (Remark 15). As we show in Theorem 13, the same result holds even for SSMs evading NONNEGATIVE when they are TIME-INVARIANT, at least 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 0 (Theorem 22).We combine Theorems 1 and 2 to derive an exact characterizations of the regular languages that modern non-time-invariant SSMs such as Mamba can recognize or predictively model -the two notions coincide here -in the finite-precision setting. The key insight is that L FF and PARITY are fundamental building blocks of two classes of regular languages: star-free languages and their complement, non-star-free languages [Schützenberger, 1965, McNaughton and Papert, 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 star operation.L FF 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.2 A language is star-free if and only if it can be defined logically using only first-order quantifiers and the order relation [Schützenberger, 1965] . Also, L is non-starfree if and only if recognizing it involves counting modulo some finite integer K [McNaughton and Papert, 1971] ; Modern non-time-invariant SSMs such as Mamba cannot perform modulo counting, but they can model all star-free languages: Theorem 4. Let L be a regular language. The following are equivalent: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 language [Schützenberger, 1965] ; hence, we have a 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 formal abstraction of transformers (masked unique hard attention) also recognizes exactly the star-free languages, but constructions of realistic transformers via Krohn-Rhodes in Liu 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 [Bhattamishra et al., 2020 , Liu et al., 2023a] . Known length-generalizing 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, we expect that the SSM architecture confers an advantage in star-free state tracking problems when compared to transformers -a prediction we will find supported experimentally (Figure 5 ).Having characterized the regular languages modeled by SSMs, we now consider languages requiring 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 example is the Dyck-1 language of well-formed strings over "(" and ")"; here a counter is incremented (decremented) whenever an opening (closing) bracket is encountered; a string is well-formed if and only if the counter is 0 at the end of the string. Some other relevant formal languages are Shuffle-Dyck-k (the shuffles of multiple Dyck-1 languages), a n b n -here, a increments the counter and b decrements it, and a n b n c n -here, there are two counters, one keeping track of a n b n and one of b n c n (See Appendix C.2). Such counter languages are fundamental as basic context-free (Dyck-1, a n b n ) or context-sensitive (e.g., a n b n c n ) languages [Hopcroft et al., 2001] , and have been the subject of studies of both transformers [Bhattamishra et al., 2020] and RNNs [Weiss et al., 2018] .Theorem 5. The languages Dyck-1, Shuffle-Dyck-k, n-ary Boolean Expressions, a n b n , a n b n c n , and a n b n c n d n , (defined in Appendix C.2) can each be predictively modeled by an SSM.The proof is in Appendix B.4. Intuitively (Figure 2 ), an SSM can directly implement the required counters by setting A ≡ 1 and by defining B(e σ ) to be the increment or decrement cased by σ. 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 t can encode unbounded counts, reading out the modular value of an unbounded integer is a formidable problem for typical neural network nonlinearities, in particular when the information has been pushed through normalization (2).We should note that there is a qualitative difference between this result and the preceding positive results about finite-state languages (Theorems 1 and 4), in that the construction in Theorem 5 uses unboundedly large entries in the state h t , whereas Theorems 1 and 4 use bounded values at finite precision. Indeed, we will find better length generalization in the finite-state case (Figure 5 ).A consequence of Theorem 5 is that SSMs can recognize some languages transcending the contextfree languages, as a n b n c n is not context-free. A second application of the theorem, of great linguistic interest, is to bounded hierarchical structure, as we discuss next.It is generally agreed that hierarchical structure is a key aspect of language, and comprehending language at a 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 a 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 a stack.A useful abstraction of hierarchical structure as relevant to natural language is the family of Dyck languages. The bounded-depth Dyck language Dyck K,h with K types of parentheses and depth h is the language of well-bracketed strings over ( 1 , ) 1 , . . . , ( K , ) K , 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ützenberger, 1963] asserts that any context-free language can be expressed as a homomorphic image of the intersection between a Dyck language and a regular language. Specifically, the Dyck language in question refers to the classical unboundeddepth 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 al., 2019] . Prior work has found that two-layer transformers [Yao et al., 2021a] and traditional RNNs [Hewitt et al., 2020 , Bhattamishra et al., 2020] both model all Dyck K,h languages. The same turns out to hold for SSMs: Theorem 6. There is a two-layer SSM with d = O(hlogK) that predictively models Dyck K,h at all input lengths, at finite precision. The proof is in Appendix B.5. Intuitively (Figure 3 ), the first layer records the depth of each parenthesis using the ideas from Theorem 5, and the second layer keeps track of the last open bracket at each depth using Theorem 1. We note that, since Dyck K,h is star-free, Theorem 4 already guarantees the existence of representing SSMs, but the depth and width guaranteed by Theorem 6 is likely to be much better than what would be obtained by a black-box application of Theorem 4: As Hewitt et al. [2020] show, h log K units is optimal up to constants and is attained by traditional RNNs and LSTMs. The SSM construction is very different from that of Hewitt et al. [2020] for traditional RNNs (both simple RNNs and LSTMs), which directly simulates a stack. Our construction is similar to the transformer construction in Theorem 4.2 in Yao et al. [2021a] , which however has to rely on specific positional encodings, unlike the SSM construction. This highlights that stacks are not the only way of simulating bounded hierarchical structure in recurrent architectures, and nonstack-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. 
experiments: 
 We have derived a fine-grained theoretical characterization of expressiveness strengths and limitations of SSMs. We now show that our positive results can be instantiated and learned in a realistic SSM implementation, by evaluating a recent highly successful SSM, Mamba [Gu and Dao, 2023] .FlipFlop We empirically instantiate Theorem 1 using the dataset of Liu et al. [2023a] , reflecting the language L FF as defined in Section 3.1. Matching Figure 2 in Liu et al. [2023a] , we evaluated both on in-distribution data, and on out-of-distribution data where the distance between read and write instructions tended to be larger. We evaluate for predicting the bits following r instructions3 , Bhattamishra et al. [2020] (orange), on in-distribution lengths (solid) and outof-distribution lengths (dotted). As predicted by Theorem 4, Mamba performs strongly on star-free languages, and even shows perfect length generalization. Again as predicted by Theorem 4, it performs poorly on non-star-free languages. Results for transformers from Bhattamishra et al. [2020] are mixed. Mamba also succeeds on learning the counter languages from Theorem 5, showing perfect accuracy at in-distribution lengths at in-distribution lengths, but length generalization lags behind transformers.matching the "deterministic/clean" mode of Liu et al. [2023a] , and considered predictions to be correct only if all predictions within a sequence were correct. (Further details in Appendix D.2). A small one-layer4 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. Mamba shows near-zero test error in both In-(green) and Out-of-distribution (orange) settings, consistent with Theorem 1, and avoids the failure seen in transformers [Liu et al., 2023a] Test Suite from Bhattamishra et al. [2020] To test our theoretical results on regular and counter languages (Theorems 2, 4, 5), we test Mamba on 27 formal languages, including 18 regular languages and 9 counter languages, based on a prior study comparing transformers and RNNs [Bhattamishra et al., 2020] . The regular languages include a popular benchmark [Tomita, 1982] and 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.Following Bhattamishra et al. [2020] , 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 et al. [2020] , we count the model's response on an input string as correct if and only if predictive modelling was successful at all positions in the input. Such a evaluation setup makes random baselines low, where a random predictor would have an accuracy exponentially small in N in each of the N 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 D.1.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 a striking confirmation of Theorem 4, Mamba learns all star-free languages with strong length generalization but performs poorly on non-star-free languages. Transformers show more mixed results, often failing to length-generalize even on star-free languages. Consistent with Theorem 5 , Mamba, like Transformers, learns counter languages but struggles more with length generalization. The differences in Mamba's performance between star-free and counter languages may stem from the fact 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 5) uses unbounded state values.Bounded Hierarchical Structure To test Theorem 6, we recreate the experimental setup from Yao et al. [2021b] . Matching their Figure 4 , we trained Mamba to predictively model Dyck K,h at K = 8 and h = 10. The training and the validation set contained samples of length ≤ 700, while the test set contained samples of length 700 ≤ n ≤ 1400. Yao et al. [2021b] found both transformers and LSTMs achieved strong performance on this setup. We provide further details in Appendix D.3. Recall that Theorem 6 shows that two-layer SSMs can predictively model Dyck K,h . We trained 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 7 ).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 conclusions 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 codebase on GitHub and added a link to it in the main paper with instructions on how to run our experiments, ensuring that our findings can be reproduced. 
discussion: 
 Related Work Our work belongs to an incipient line of research into the expressiveness of SSMs [Jelassi et al., 2024 , Merrill et al., 2024] . It is 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 [e.g. Chiang et al., 2023 , Merrill and Sabharwal, 2023 , Strobl et al., 2024] . A second link is to 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 a 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 on SSM-based LLMs. First, encouragingly, SSMs can keep track of bounded hierarchical structure with optimal memory even without explicitly implementing a stack (Theorem 6), suggesting that simple diagonal linear state updates may be sufficiently powerful for modeling the hierarchical structure of language. Second, SSMs resolve a basic failure mode of self-attention in flip-flop state tracking while being parallellizable (Theorem 1). Overall, SSMs and attention have overlapping but distinct strengths. This lends support to the development of hybrid architectures interleaving SSM and attention layers, as instantiated very recently by Jamba [Lieber et al., 2024] . Third, nonnegative gates as obtained by exponential or sigmoid parameterizations provably restrict expressive capacity, even in non-time-invariant SSMs (Theorem 2). While Gu and Dao [2023] found no evidence that complex-valued paramerizations improved 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 characterizing the capacity of transformers has proven difficult even in the finite-state case, Theorem 4 provides a 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 expressiveness, 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 a learnable manner, in one realistic SSM implementation, implementational 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.Question: Does the paper provide open access to the data and code, with sufficient instructions to 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 on how to run our experiments.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
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, a 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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 a 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 to a 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. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate 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% or 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.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs 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 (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We have verified compliance with the NeurIPS Code of Ethics, Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 we foresee no positive or negative societal impact of the results.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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 specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not 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, it 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 as 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 or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation 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). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: We are not releasing data or models, and foresee no risk of misues of our theoretical results. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring 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 not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: 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? 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 use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• Depending on the country in which research is conducted, IRB approval (or equivalent) 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. 
 
 Appendix: Here, we survey how (1) is instantiated in a range of SSMs. As stated in Section 2.1, we refer to SSMs where the gate A does not depend on x t as time-invariant. An equivalent terminology is the distinction between "Weak Linear Time Invariant Convolutional Models" (i.e., time-invariant) and "Linear Time Variant Models" (i.e., non-time-invariant) in Akyürek et al. [2024] .Approximately simultaneously with or more recently than Gu and Dao [2023] , a range of non-timeinvariant SSMs have been introduced [De et al., 2024 , Yang et al., 2024 , Qin et al., 2024b,a] . This category also covers highly similar earlier RNN variants [Bradbury et al., 2016 , Lei et 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 a matrix multiplication Ah t-1 instead of elementwise multiplication A(x t ) • h t-1 in (REF), but importantly, Mamba's A is diagonal, so we can take A(x t ) i = A ii . Due to exponential parameterization, its entries are nonnegative.Griffin The RG-LRU layer of Griffin [De et al., 2024] uses the equationh t = a t A(x t ) •h t-1 + 1 -a 2 t • (i t • x t ) B(x t )where a t , i t are neurally parameterized in terms of x t but not h <t ; by design, a t ∈ (0, 1). φ is instantiated in terms of linear transformations, GeLU, and RMSNorm (Figure 2 in De et al. [2024] ). The local attention used by Griffin can be subsumed into an SSM layer (Remark 19).Gated Linear Attention [GLA Yang et al., 2024] This model (Section 4.4 in Yang et al. [2024] ) instantiates our framework using a recurrence of the form (1); while the state is two-dimensional in this model, the update is performed by elementwise products as in (1). The gate is obtained by applying sigmoid to a linear transformation of x t ; thus, its entries are in (0, 1). φ is instantiated in terms of SwiGLU and LayerNorm.HGRN HGRN [Qin et al., 2024b] and HGRN2 [Qin et al., 2024a] are defined by a recurrence of the form (1); the gate entries are ∈ (0, 1) by design. φ is instantiated in terms of GLU, linear transformations, and normalization. In HGRN, the state is complex, but crucially the gate remains real-valued.Time-invariant SSMs introduced before late 2023 are surveyed by Gu and Dao [2023, Appendix B] , such as [Mehta et 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 a 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 13.Note also that Ah t-1 is often described as a general matrix multiplication, but A is diagonalizable (e.g. Lemma 3.2 in Gu et al. [2021] ; Sun et al. [2023] for RetNet), which -even though implementation may be based on non-diagonalized representations [Gu et al., 2021 ]-renders the model equivalent to one where A is diagonal from the start. This equivalence is shown as Lemma 3.1 in Gu et al. [2021] .We begin by introducing key notions of automata theory. References for automata theory include Eilenberg [1974] , Hopcroft et al. [2001] , Sakarovitch [2009] . We will provide those key notions that are necessary to prove our results. We will focus on deterministic finite-state-automata (DFA), and simply refer to them as finite-state-automata.5 First, Definition 7. A (deterministic) finite-state-automaton A consists of:• a finite alphabet Σ • a finite state set Q • a starting state q 0 ∈ Q • a transition function u : Q × Σ → Q We extend u to a map u : Q × Σ * → Q by setting: u(q, ε) = q u(q, w 1...i+1 ) = u(u(q, w 1...i ), w i+1 )where ε is the empty word.Intuitively, u(q 0 , w) is the state that A is in after reading w.The automaton recognizes a language L ⊆ Σ * if there is a recognizing set R ⊆ Q such that L := {w : u(q 0 , w) ∈ R} (4)Kleene's Theorem [Kleene, 1951] asserts that a language L ⊆ Σ * is regular (i.e., defined by a regular expression) if and only if it is recognized by some finite-state automaton.A very fundamental automaton underlying Flip Flop is: Definition 8. A set-reset automaton is a finite-state-automaton whereEQUATIONIntuitively, such an automaton keeps recording the last seen symbol from a designated set Q ⊆ Σ. Such an automaton is easily simulated with a single non-time-invariant SSM layer:Lemma 9. Let A = ⟨Σ, Q, q 0 , u⟩ by a set-reset automaton. Then there is a single-layer SSM with finite precision and width d = 1 + log Q that maps each w 1...T ∈ Σ * to the state sequence u(q 0 , w 1 ), u(q 0 , w 12 ), . . . , u(q 0 , w 1...T ) ∈ Q T .Formally, there is an injective map V : Q → R d such that ρ(z t ) = V (u(q 0 , w 1...t )) for t = 1, . . . , T .Proof. Let B(σ) ∈ R log |Q| be a binary encoding if σ ∈ Q, and 0 ∈ R log |Q| else. Take h 0 = B(q 0 ). Let A(σ) = 0 if σ ∈ Q and A(σ) = 1 else. After processing a string, the state h t is B(σ) where σ is the last symbol in Q that has occurred if any has, and B(q 0 ) otherwise. Coming to (2, in order to avoid division by zero when normalizing if no element of Q has been read, we add a dummy dimension to h t whose value is always 1. We take Mix 1 , Mix 2 to be the identity. Note that, even though normalization will affect the numerical values, the binary encoding of σ ∈ Q can still be read out with finite precision, as 1 ≤ ∥h t ∥ 2 ≤ 1 + log |Q|, and thus nonzero entries will remain bounded away from zero.Theorem 10 (Restated from Theorem 1). There is a two-layer SSM that predictively models L FF at all lengths, at finite precision.Proof. In the first layer, we use Lemma 9 to simulate a set-reset automaton over the input alphabet Σ 1 = {w, r, i, 0, 1} where Q 1 = Σ 1 ∪ {q 0 }. 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, ρ(h t ) allows us to read out the input symbols x t-1 , x t ∈ Σ.In the second layer, we again use Lemma 9 to simulate a set-reset automaton over an extended alphabet Σ 2 := Σ 1 × Σ 1 , where the first component indicates the input symbol x t and where the second component indicates x t-1 . In this set-reset automaton, Q 2 contains, besides a start state q 0 , those elements of Σ 2 whose second entry is w. The second layer thus keeps track of the input bit b ∈ {0, 1} following the last write instruction. It additionally forwards the input symbol x t using additional dimensions.The second layer, via ρ, then predicts the possible next symbols on the basis of this information: If x t ∈ {0, 1}, any instruction in {w, r, i} is possible. If x t ∈ {w, i}, any bit in {0, 1} is possible. If x t = r, 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, 1} is possible.Definition 11. PARITY is the regular language over Σ = {0, 1} of strings where the number of ones is even. As a regular expression, PARITY is (0 * 10 * 10 * ) * .Theorem 12 (Restated from Theorem 2). No SSM satisfying NONNEGATIVE can recognize PARITY at arbitrary input lengths with finite precision.Proof. We consider an SSM with multiple layers, and indicate the layer in superscript: hEQUATIONt . We write z (0) t for the input token embedding e(w t ). Consider a SSM processing the word 1 t , for t → ∞. We show, by induction over the number of layers, the following claim:( †) Each entry of z (k)t converges to a value bounded, in absolute value, by a constant. By the assumption of finite precision, convergence automatically leads to the entries becoming ultimately constant. Once we have shown this, we know that z (L) t is constant when t is sufficiently large; thus, the parity of the string 1 t cannot be read out from z (L) t . As a 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 14.We proceed to proving ( †). The claim ( †) is trivially true at k = 0, as the input token is always the same and we defined z (0) t := e(w t ). Now consider k > 0. By hypothesis, the activations are given asEQUATIONwhere A(x t ), B(x t ) are constant α := A(x t ), β := B(x t ) when t > T 0 , for some T 0 > 0. The solution of the recurrence for t > T 0 isEQUATIONEach dimension j = 1, . . . , d of this vector can be constant (if (h T 0 ) j + β j α j -1 = 0), diverge exponentially (α j > 1), converge exponentially (α j < 1) or diverge linearly (α j = 1).We next need to show that z t = Mix 2 (Norm(Mix 1 (h t , x t ))) converges.First, consider the effect of applying a linear transformation to the state h t . Each entry of the result will be some linear combinationEQUATIONIf each α j < 1, then u t converges. If some |α j | ≥ 1, there may be some cancellation if α i = α j 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 u t will again either converge to a finite value or diverge towards ±∞.We now need to understand the behavior of Mix 1 (h t , x t ). Recall that, based on our survey (Appendix A), we allowed it to contain linear, GLU [Dauphin et al., 2017] , and SwiGLU [Shazeer, 2020] components. If Mix 1 (h t , x t ) implements a linear transformation only, each entry likewise may converge, diverge linearly, or diverge exponentially. We note that-if σ is the sigmoid functionσ(u t ) always converges, as σ simply saturates to 0 or 1 if u t diverges. Hence, if Mix 1 (h t , x t ) implements GLU, each entry likewise may converge, diverge linearly, or diverge exponentially. Finally, if Mix 1 (h t , x t ) implements SwiGLU, each entry of the result will be a product of a linear combination of the form u t , and Swish β applied to another such linear combination. Depending on the behavior of these two u t -like terms, the outcome will behave as a product of sequences that may converge exponentially, diverge exponentially, or diverge linearly -e.g., the outcome may also diverge quadratically, or converge as nα -n , etc.If all dimensions of Mix 1 (h t , x t ) converge, then Norm(Mix 1 (h t , x t )) will also converge to a scaled version of β i 1-α i , scaled by a bounded factor as β i ̸ = 0. Now assume some dimensions of Mix 1 (h t , x t ) do not converge; in this case, for any two dimensions i, j, either their ratio will converge to a constant, or converge to 0 or ±∞. After applying Norm(•), the entries asymptotically dominating the others will converge to a finite value bounded, in absolute value, by 1; the others will converge to zero.In conclusion, we have found that each entry of Norm(Mix 1 (h t , x t )) converges to some number bounded, in absolute value, by 1. As Mix 2 is continuous, each entry of z t likewise converges, with a bound depending on the Lipschitz constant of Mix 2 .We next show the result, referenced in the main paper text after Theorem 2, about time-invariant SSMs with complex-valued 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 A has a rational angle in the complex plane.Here, by a rational angle, we refer to an angle that is a rational number when expressed in degrees; such angles are rational multiples of 2π when expressed in radians. As the rational angles are dense in the reals, one expects that even if some irrational angles permitted modeling PARITY, such solutions would be very hard to find -in particular given that irrational numbers are not exactly represented in finite precision.Proof. By assumption, any A j ∈ C in any layer can be written asEQUATIONwhere q j ∈ [0, 1] is rational and r j ≥ 0 is real -here, 2πq j is known as the argument of A j ; it describes the angle of A j in the complex plane in radians. Correspondingly, the angle in degrees is described by q j • 360 • ; this is rational if and only if q j is.As a time-invariant SSM has a finite number of such values A j , across all its layers, we can select a positive integer W such that W q j ∈ N for each j, in each layer. Importantly, (A j ) W = (r j ) W ∈ R.Now consider the action of any layer of the SSM on an input sequence of the form A T = (10 W -1 ) T .The claim is that, for each i = 1, . . . ,W , the sequenceEQUATIONconverges as t → ∞. As in the proof of Theorem 2, in the finite-precision setting, converge entails that the sequence becomes ultimately stationary. Note that the parity of A T equals the parity of T ; hence, it is impossible to read out the parity from z(k)TW when T is large. Now consider, suppressing the index for the dimension in 1, . . . , d:h (k) tW = tW ∑ i=1 A tW -i B(z (k-1) i ) = tW ∑ i=1 A tW -i B(z (k-1) i ) = t ∑ s=1 (s+1)W -1 ∑ j=sW A tW -j B(z (k-1) sW + j ) = t ∑ s=1 W -1 ∑ j=0 A (t-s)W -j B(z (k-1) sW + j ) = t ∑ s=1 W -1 ∑ j=0 (r exp(2πiq)) (t-s)W -j B(z (k-1) sW + j ) = t ∑ s=1 W -1 ∑ j=0 r (t-s)W -j exp(-2πi jq)B(z (k-1) sW + j ) = W -1 ∑ j=0 exp(-2πi jq) t ∑ s=1 r (t-s)W -j B(z (k-1) sW + j )Separately considering summation beyond T 0 at which z(k-1)tW + j has become stationary, we get= T 0 -1 ∑ j-0 . . . U 1 +       W -1 ∑ j=T 0 exp(-2πi jq)B(z (k-1) j )r -j U 2 t ∑ s=1 r (t-s)W U 3      U 1 and U 2 do not depend on t. Intuitively, U 2 ∈ C determines a direction in the complex plane, whereas U 3 ∈ R determines a magnitude. It remains to understand U 3 , which can be rewritten as:EQUATIONWe have now achieved a situation like in the proof of Theorem 2: U 3 can converge exponentially, diverge linearly, or diverge exponentially. The remainder of the proof is analogous to that proof.The following Corollary of Theorem 2 will be used in the proof of Theorem 4: Corollary 14. Assume NONNEGATIVE, SSMs with finite precision cannot recognize any non-starfree regular language.Proof. For any non-star-free regular language L, there are words u, v, w such that the membership uv n w ∈ L is determined by the value of n modulo some finite integer k (depending on L) [Mc-Naughton and Papert, 1971] . Fix any such u, v, w ∈ Σ * . Now assume an SSM satisfying NONNEGATIVE can recognize L with finite precision. We can subsume the action of u into the state h 0 by taking h 0 , in each layer, to be the state of the SSM after reading u. We now have an SSM that can determine the parity of t when fed a word of the form v t w.For this SSM, we want to show ( †) When fed words of the form v, v 2 , v 3 , . . . , for each i = 0, . . . , |v| -1, and each layer k = 1, . . . , L, the sequence z(k)t|v|+i converges as t → ∞.As in the preceding two proofs in this section, convergence entails becoming ultimately constant in the finite-precision setting.The claim ( †) is immediate at k = 0. Now at k > 0, we write:h (k) t|v|+i =A(z (k-1) t|v|+i ) . . . A(z (k-1) (t-1)|v|+i+1 )h (k) (t-1)|v|+i + A(z (k-1) t|v|+i ) . . . A(z (k-1) (t-1)|v|+i+2 )B(z (k-1) (t-1)|v|+i+1 ) + A(z (k-1) t|v|+i ) . . . A(z (k-1) (t-1)|v|+i+3 )B(z (k-1) (t-1)|v|+i+2 ) + . . . + B(z (k-1) (t-1)|v|+i )On the RHS, as t → 0, all terms except for h (k) (t-1)|v|+i become constant by the inductive hypothesis. Hence, there are some α, β such that, for sufficiently large t, hEQUATIONWe are now, for each i, in the same situation as in the proof of Theorem 2]: each dimension of this recurrence can converge exponentially, diverge exponentially, or diverge linearly; as in that proof, it follows that z(k)t|v|+i converges as t → ∞. We have shown ( †).We now follow up by showing that ( * ) When fed words of the form v t w, for each i = 1, . . . , |w|, and each layer k = 1, . . . , L, the sequence z (k) t|v|+i converges as t → ∞. Again, at finite precision, convergence entails that the sequences are ultimately constant. Again, ( * ) is true at k = 0 trivially. When feeding the SSM words of the form v t w, in each layer, the final state is in each layer k, at each i = 1, . . . , |w|:h (k) t|v|+i =A(z (k-1) t|v|+|w| ) . . . A(z (k-1) t|v|+1 )h (k) t|v| + A(z (k-1) t|v|+i ) . . . A(z (k-1) t|v|+2 )B(z (k-1) t|v|+1 ) + . . . + B(z (k-1) t|v|+i )By inductive hypothesis, for large t, there are ψ i , γ i such thath (k) t|v|+i =ψ i • h (k) t|v| + γ iand, as shown before, each entry of h (k) t|v| converges exponentially, diverges exponentially, or diverges linearly. Now, by assumption, one can read out, at finite precisiion, the parity of t fromz (L) t|v|+|w| = Mix 1 (Norm(Mix 2 (ψ |w| • h (k) t|v|+i + γ |w| )))We now simply absorb the operation X → ψ |w| •X +γ |w| into Mix 2 , and obtain by the same arguments as in the proof of Theorem 2 that z (L) t|v|+|w| converges as r → ∞. This is a contradiction to the claim that the value of t can be read out, modulo k, from z (L) t|v|+|w| at finite precision. Remark 15. As outlined in our analysis, the assumptions in Theorem 2 are based on layer-wise operations that are either linear or based on the GLU or SwiGLU activation functions. This assumption is critical to the proof: one could design activation functions that make PARITY expressible.Given a sequence x = x 1 , . . . , x T , consider the function f (x) = e iπ ∑ n i=1 x i +1 2. This continuous function is designed to satisfy the condition that, for bit-strings x, f (x) = 1 if ∑ n i=1 x i is even, and f (x) = 0 otherwise. At first glance, it seems like this function can be approximated by a cumulative sum layer in combination with a two-layer SSM to compute f (x) = e iπx +1 2 . However, this construction cannot be implemented under the condition for which we prove Theorem 2. This is because computing this function f (x) inherently requires a layer-wise nonlinear operation (such as a MLP) capable of representing sine and cosine functions over arbitrarily large input values. Importantly, achieving a construction that works for any input length requires the ability to handle arbitrarily 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 p 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 C b (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) = e iπx +1 2 in a typical MLP architecture.Thus, it is unrealistic to expect a typical MLP, with ReLU or sigmoid activations, to implement the function f (x) = e iπx +1 2 uniformly for arbitrarily large inputs. Consequently, a 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, as these adjustments fall outside the scope of the assumptions made in our proof. 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 of Wang and Xue [2024] , and further emphasized by Orvieto et al. [2024] . in their Remark 2. Our results, in contrast, pertain to the existence of a single SSM capable of recognizing a formal language for any input length, independent of network size. Thus, such universal approximation results do not undermine Theorem 2.Our proof of Theorem 4 will rely on the algebraic theory of finite automata, specifically the cascade product and the Krohn-Rhodes 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-generalizing implementations of these algebraic notions than what is possible for transfomers.Recall the definition of a finite-state-automaton (Definition 7). Our construction will build on an important operation on automata, the cascade product [Krohn and Rhodes, 1965 , Eilenberg, 1974 , Ginzburg, 1968] :EQUATION)the cascade product A 2 ≀ A 1 is the automaton given by• Σ = Σ 1 • Q = Q 2 × Q 1 • q 0 is the tuple of the starting states of A 2 , A 1 • u(⟨q, p⟩, σ) = ⟨u 2 (q, ⟨p, σ⟩) , u 1 (p, σ)⟩We note that the literature usually uses "•" for the cascade product [e.g. Eilenberg, 1974] . To avoid collision with the elementwise product "•" (e.g., ( 1)), 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 A 1 , recording the state sequence q 0 , q 1 , . . . , q |w| ∈ Q 1 and -at each t = 1, . . . , |w| -pasting the state q t-1 together with the input symbol w t ∈ Σ 1 -resulting in a word over a new alphabet Q 1 × Σ 1 , and then running A 2 on the resulting word. The overall state of A 2 ≀ A 1 after reading a word is the tuple of the states reached by A 2 and A 1 . Note that we write A 2 ≀ A 1 , rather than, A 1 ≀ A 2 , because the second argument of the cascade product (A 1 ) intuitively reads the input first, preprocessing it for the other automaton, A 2 -the cascade product can thus be viewed as a kind of function composition.The somewhat inscrutable update rule for u(•, •) encodes the action of A 1 in the second component, and the action of A 2 on the extended alphabet in the first component. There is a close analogy to 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-Rhodes Theorem [Krohn and Rhodes, 1965 ] and Schützenberger's Theorem [Schützenberger, 1965] ). Each star-free regular language is recognized by an iterated cascade product of set-reset automata, (. . . (A 1 ≀. . . )≀A n-1 )≀A n , where each A i is a set-reset automaton.This result follows from the Krohn-Rhodes decomposition theorem [Krohn and Rhodes, 1965] , which states that any finite-state automaton can be expressed as an iterated cascade product of simple 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 auxiliary lemma, which provides a single-layer SSM that encodes the input w t-1 in state h t -we will use it to forward information about the state of A 1 at t -1 to A 2 at t:Lemma 18. Let Σ be an alphabet, and consider words w ∈ Σ * . There is a one-layer SSM with d = 4|Σ| such that, for t = 2, . . . , |w|, the character w t-1 can be read out from z t at finite precision.To prove Lemma 18, a first idea is to use an exponential moving average with A = 1/2 to encode the recent input characters in h t ; this effectively encodes the full history into the binary expansion of h t , 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 second-most-significant bit. 6 We avoid this problem simply by taking A = 1/4, effectively utilizing only every two digits in the binary expansion of h t , ensuring that the second-last input can be read out at 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, andh 0 = [0, 0, 0, 0] T A(e 0 ) = [1/4, 1/4, 0, 0] T A(e 1 ) = [1/4, 1/4, 0, 0] T B(e 0 ) = [1, 0, 1, 0] T B(e 1 ) = [0, 1, 0, 1] TNow we separately consider the state h t depending on the form of the prefix w 1...t (here w 1...t refers to first t characters in the word). If w 1...t = . . . 00 (the last 2 characters of the prefix are 00), thenh t =    ∈ [1, 2] ∈ [0, 1/8] 1 0    (14) because h t =A(e 0 ) • h t-1 + B(e 0 ) =A(e 0 ) • A(e 0 ) • h t-2 + A(e 0 ) • B(e 0 ) + B(e 0 ) =[1/16, 1/16, 0, 0] T • h t-2 + [1/16, 1/16, 0, 0] T • [1, 0, 1, 0] T + [1, 0, 1, 0] T =     1 16 (h t-2 ) 1 + 1 16 + 1 1 16 (h t-2 ) 2 1 0    By definition of A and B, each entry in h t-2 is in [0, 2]; the claim ( 14) then follows. If w 1...t = . . . 10, then, by a similar calculationEQUATIONIn particular, assuming w t = 0, one can read off w t-1 from (h t ) 2 with a margin of size 1/8. As w t is encoded in h t and due to symmetry, analogous statements hold when w t = 1. Now, for each σ ∈ Σ, we run such a one-layer SSM where 0 represents σ and 1 represents all other characters.7 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|Σ| from whose states one can read out w t-1 at finite precision. As the entries in h t are all bounded by 2, we find ∥h t ∥ 2 ≤ 2 √ d independent of t, and the margin is still bounded away from zero after normalization, and thus in z t , where we can assume Mix 1 , Mix 2 to be the identity.Remark 19. Some SSMs include local convolutions [e.g. Fu et al., 2023, Gu and Dao, 2023] or local attention [De et al., 2024] , which aggregate information from a local window of some width ∆ > 0. These do not increase the expressive capacity beyond SSMs as we have defined in (1-2), as aggregation of local information can be simulated with a single SSM layer: Using the layer constructed in the proof of Lemma 18, given the state h t , once one has read out w t-1 as described in the proof, one can recover h t-1 from h t and x t ; then inductively read out w t-2 using h t-1 and x t-1 , etc. Thus, up to any given width ∆ > 0, one can read out w t-∆ , . . . , w t-1 from the state h t of this layer at finite precision.We are now ready to translate cascade products into SSM stacking: Lemma 20. Let A 1 , A 2 be two finite-state-automata, and assume that there are two SSMs with top-level states z (L 1 ,1) and z (L 2 ,2) that map each w to the state sequences under A 1 , A 2 , at finite precision.Formally, on a word w, ρ 1 (z(L 1 ,1) t ) and ρ 2 (z (L 2 ,2) t) provide the state sequences of A 1 , A 2 . Then there is an SSM with L 1 + L 2 + 1 layers that maps each w to the state sequence under A 2 ≀ A 2 , again at finite precision.We note that a conceptually related result holds for transformers [Lemma 12 in Liu et al., 2023b] . However, SSMs allow a simpler and length-independent construction, as they do not require positional encodings to implement such a construction.Proof. The lower layers are based on the SSM modeling A 1 . 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 ≡ 1, Mix j ≡ Id on these dimensions.In the resulting SSM, z L 1 t indicates both w t itself, and the state reached by A 1 after reading w 1...t .The state is redundantly indicated by two separate sets of d dimensions; the character w t is indicated by d further state.Note, however, that the second automaton in the cascade product requires access to the state q t-1 rather than q t . For this, we add a layer provided by Lemma 18, of width 4|Q|. Additional 2d dimensions pass on (1) w t , and (2) the state that A 1 reaches after reading the prefix w 1...t .We now have L 1 + 1 layers where z L 1 +1 t has 2d + 4|Q| dimensions and indicates (1) w t , (2) the state that A 1 reaches after reading the prefix w 1...t , (3) the state that A 1 reaches after reading the prefixw 1...t-1 .The first and third piece of information are now 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 4|Q|-dimensional component indicating (3), providing the desired second-to-last state.We have constructed an SSM with L 1 + L 2 + 1 layers, where z L 1 +L 2 +1 t indicates (1) w t , (2) the state that A 1 reaches after reading the prefix w 1...t , (3) the state that A 2 reaches after reading the prefix w 1...t pasted with the state sequence of A 1 . This information is sufficient for reading out the state sequence of A 2 ≀ A 1 .Note that the number of channels may not be consistent, as it is 3d in the top and bottom parts, but 2d + 4|Q| in the middle; we simply pad to the larger dimensionality.We are now ready to show the existence of length-generalizing 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 equivalent: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:1. SSMs at finite precision can predictively model all star-free languages. For each language, a single SSMs is applicable at arbitrary lengths.2. Assuming NONNEGATIVE, finite-precision SSMs cannot recognize any non-star-free regular 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 9 and 20, there is an SSM that computes the state sequence of that automaton. Now we note that, since A recognizes L, the state q 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 are words w, w ′ such that u(q 0 , w) = u(q 0 , w ′ ) and σ ∈ Σ such that wσΣ * ∩ L ̸ = / 0 but w ′ σΣ * ∩ L = / 0; then u(q 0 , wσ) = u(q 0 , w ′ σ) but the set R (4) is reachable from u(q 0 , wσ) but not u(q 0 , w ′ σ), contradiction.Hence, the SSM's outputs can be transformed, by composing ρ with a map from states to nextcharacter sets, to predictively model L.Theorem 22. SSMs with complex-valued coefficients evading both NONNEGATIVE and TIME-INVARIANT can represent all regular languages known to be in TC 0 .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-INVARIANT can count modulo any integer k, using d = 1 and A(e 1 ) = e 2πi/k , A(e 0 ) = 1, B ≡ 0, h 0 = 1. This is a generalization of the construction for PARITY described in Section B.2, since e 2πi/2 = -1.The set of regular languages known to be in TC 0 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 of 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.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 : Σ → Z C be given. Let L ∈ N. Then a one-layer SSM with finite precision can compute, at each position i = 1, . . . , T :EQUATIONin the sense that ρ can read this out from z(1)i with finite precision.Proof.Define d = 2L + 1. Define h 0 = 0 ∈ R d . For each x ∈ Σ, define A(e x ) = 1 ∈ R d and B(e x ) i ∈ R d by B(e x ) i = u(x).In order to read out the state h t up to a limit L, we defineEQUATIONBy testing which entries of the result are negative or positive, one can read out the state up to L even after rounding φ(h t , x t ) to finite precision. The proof straightforwardly extends to multiple counters.We are ready to prove the theorem:Theorem 24 (Restated from Theorem 5). The languages Dyck-1, Shuffle-Dyck, n-ary Boolean Expressions, a n b n , a n b n c n , and a n b n c n d n , (defined in Appendix C) can each be predictively modeled by an SSM.Definition 25. The language Dyck K,h [Hewitt et al., 2020 , Yao et al., 2021b] is given by the CFG with the nonterminals {S 0 , S 1 , . . . , S h-1 , S h } and the following production rules:S h →( 1 S h-1 ) 1 | . . . |( K S h-1 ) K |ε S h-1 →( 1 S h-2 ) 1 | . . . |( K S h-2 ) K |ε . . . . . . S 2 →( 1 S 1 ) 1 | . . . |( K S 1 ) K |ε S 1 →( 1 S 0 ) 1 | . . . |( K S 0 ) K |ε S 0 →εand the start symbol S h .Theorem 26 (Restated from Theorem 6). There is a two-layer SSM with d = O(hlogK) that predictively models Dyck K,h at all input lengths, at finite precision.Proof. In the first layer, we calculate each token depth up to h using Lemma 23. After the first layer, at 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, . . . , h} × {( 1 , ) 1 , . . . , ( K , ) K }. We then, for each depth l = 1, . . . , h, define a set-reset automaton (Definition 8) given by the set Q l := {l} × {( 1 , ) 1 , . . . , ( K , ) K }. 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 h ′ 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 a second SSM layer using Lemma 9. We need h such automata, and each SSM has width log K.This language is recognized by a counter automaton [Fischer et al., 1968a] .Others We further include the languages of the forms a n b n , a n b n c n , and a n b n c n d n . All experiments used the Mamba reference implementation8 . xUnless stated otherwise, we followed the defaults given there ( d state = 16, d conv = 4, expand = 2), as we found the default combination to work better than other options. We tuned d model for each language.D.1 Test Suite from Bhattamishra et al. [2020] Data Preparation For all the languages, we use either the data prepared by Bhattamishra et al. [2020] or-where not available-their data-generation scripts, allowing full comparability with results they reported for transformers. We used their official code and data release at https://github.com/satwik77/Transformer-Formal-Languages (last commit 48eea2e; MIT license). Training sets typically consist of 10K samples, with lengths varying between 1 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 n b n , where the number of positive examples in each bin was limited, all possible examples for that bin are included.Hyperparameters For each language, we conducted extensive hyperparameter search. We varied the d model parameter in Mamba across the set {16, 32, 64, 128, 256}. Additionally, we experimented with the number of layers in our model, ranging from 1 to 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, we increased the number of layers up to 12, with little to no success.We used the AdamW optimizer. To identify optimal learning rates, we started with a coarse hyperparameter search using values from the set {0.001, 0.0001, 0.00001}. If one of these learning rates showed high performance, we conducted a more fine-grained search to find the optimal learning rate. Finally, we varied the batch size from {16, 32, 64} for datasets with 10K training examples.For languages like a n b n with limited training size, we searched for an optimal batch size within the set {5, 10}.We obtained the dataset of Liu et al. [2023a] from their release, https://huggingface.co/ datasets/synthseq/flipflop (MIT license). Our setup corresponds to the deterministic ("clean") mode in Liu et al. [2023a] . Matching Figure 2 Bhattamishra et al. [2020] . For Mamba, we report best settings (chosen based on inputs of length [1, 50] ) at 1 (Mamba1), 2 (Mamba2), 3 (Mamba3) layers.Results for the best-performing layer count are also shown in Figure 5 .We built on the official code and data release of Yao et al. [2021b] at https://github.com/ princeton-nlp/dyck-transformer (last commit: 5d21fcf). We train a 2-layer Mamba and a 1-layer Mamba on Dyck K,h 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 ≤ n ≤ 1400. We train Mamba with a varying number of layers l ∈ {1, 2} and d model ∈ {20, 30, 40, 50, 60, 70, 80, 90, 100}. Results for the best-performing layer count are also shown in Figure 5 .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), we select the learning rate with the better training performance.As described in Section 2.1, 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 a sufficiently large constant (e.g., p = 8), independent of the length of the input.There are a variety of related precision notions in the theoretical literature on 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 a setting is unrealistic, as it would allow encoding arbitrary detail about the input into infinite precision [e.g. Siegelmann, 1999] and read these out with sufficiently powerful functions (A, B, φ) 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 a setup may be justified based on the fact that any real computer has bounded memory, 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced.• 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 to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be 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., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In 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 to have some path to reproducing or verifying the results.Code is available at: https://github.com/lacoco-lab/ssm_expressivity 38th Conference on Neural Information Processing Systems (NeurIPS2024).For example, (01) * is star free. It is the union of ε with the intersection of 0Σ * , Σ * 1, with the complements of Σ * 00Σ * and Σ * 11Σ * .Predictive modeling is trivial at other positions, as only the input symbols need to be considered there.Theorem 1 constructs a two-layer SSM. We hypothesize that Mamba uses its local convolution (Remark 19) to replace the lower layer from the construction in Theorem 1.A closely related notion is the semiautomaton, which is the notion considered in the closely related workLiu et al. [2023b]. Semiautomata lack a fixed start state q 0 . We include q 0 , but this difference is not substantial for our formal results.Informally, in binary, 0.0111111...111 and 0.1 are arbitrarily close.In fact, using a binary encoding of Σ, one can achieve d = 4 log |Σ|.https://github.com/state-spaces/mamba/blob/main/README.mdFrom https://github.com/state-spaces/mamba/blob/main/README.mdFor instance, a Turing machine with bounded memory and thus a bounded tape is equivalent to a finite-state automaton. 


Decision: 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.

Reviews: review: paper_summary: paper_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.

Due 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.
strength_weakness: strength_weakness: 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, 
- 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?
- at l.215: “L is non-star-free if and only if recognizing it involves counting modulo some K.” What is K?
- 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.
- What is Chomsky–Schützenberger theorem?
questions: 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)?

- Some authors claim that neural networks are Turing complete. For example,

  [PMB19] _Jorge Pérez, Javier Marinković, Pablo Barceló, On the Turing Completeness of Modern Neural Network Architectures, ICLR2019_

  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: limitations: n/a
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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?
- 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.
questions: 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?
- 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: limitations: Already addressed by authors.
paper_summary: paper_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.

In more detail, the paper presents the following results:
- 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).
- The class of non-negative, finite precision SSMs predicts exactly the star-free languages (Theorem 4).
- Various kinds of languages that require unbounded counting, such as Dyck languages, $a^nb^nc^n$, or boolean expressions, are predicted by an SSM.

In 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.
strength_weakness: strength_weakness: The clarity and quality of the paper could be improved. This is mainly due to three reasons:
- 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.

- 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. 
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.

- 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.
questions: 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? 
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.
limitations: 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.
paper_summary: paper_summary: 1. This paper studies the expressive capacity of state-space models from a formal language perspective. 
2. It shows that for flip-flop, SSM can do well. And for parity, SSM cannot do well.
strength_weakness: strength_weakness: 1. The theorem 2 seems to be problematic:
	1. 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. 
	2. 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:
		1. https://openreview.net/forum?id=i0OmcF14Kf
		2. https://arxiv.org/abs/2307.11888
		3. They are also related works in the expressive sense.
		4. Still it is possible to have the unboundedness issue from $\sum_{i=1}^n x_i$. 
		5. 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. 
		6. I am willing to raise the score if this issue can be better discussed. 
	3. 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. 
2. The role of parameterization discussed in page 3 seems a bit lacking of related work
	1. HIPPO(https://arxiv.org/abs/2008.07669), Approximate Diagonalization(https://arxiv.org/abs/2310.01698), StableSSM(https://arxiv.org/abs/2311.14495).
3. Line 682, typo - have shown.
questions: 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. 
2. 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: limitations: 1. The result derived in this paper is limited to formal languages. It is not clear what is the generalization to natural languages.

Comments: title: Related work, just a comment
comment: Thank you so much for the discussion, and your suggestions. We are grateful for your recommendation
Thanks for getting back to me. 

I stand with my initial rating and recommend this submission to accepted.
We are pleased to hear that your concerns have been addressed. Thank you so much for your feedback and suggestions
Thank you for the detailed explanation. My issue has been thoroughly and clearly resolved. I’ve updated my score from 4 to 6.
We will include our responses to the questions raised in the appendix for clarity, as suggested. We are delighted to know that we were able to convey the importance of our theoretical results and are grateful to the reviewer for increasing their score.
Thank you for your detailed response. I would like to increase my score based on your responses to my questions. I am convinced that the theoretical contributions are worthy enough to be published now.

It would be very helpful for readers to add Responses to Questions to the paper/appendix.
We are pleased to hear that your concerns have been addressed and are grateful for your strong acceptance rating. Thank you so much for your feedback and suggestions.
1. Authors said that they "will include additional intuitive explanations and visual aids" in the paper.
2. Zubić et al. work will be included in the Related Work section.
3. Authors said that they "will thoroughly proofread the paper again and carefully correct all the typos we missed".
4. In the follow-up work they can also do more experiments for various tasks.
5. Authors discussed that probably Attention + SSMs will be the future of Neural Net Architectures.

Therefore, everything I had as problem is addressed, and I will finalize my rating as:

8: Strong Accept
Yes, that's correct. Our positive results on Flip-Flop, Star-Free, and bounded-depth Dyck languages (Theorems 1, 4, 6) would not be affected and remain valid even under the more restricted definition of finite precision, i.e., "full" finite precision. Similarly, our negative results regarding Parity and non-star-free languages would also remain unaffected (Theorems 2, 4). Only Theorem 5 (unbounded counting) would be invalid under full finite precision. We discuss this briefly in Appendix E (lines 1046 to 1068). We hope this clarifies your question. However, please let us know if further details are needed on this issue.
Thank you for your clarifications. I appreciate your willingness to improve the clarity of some of your proofs.

However, I have a follow-up question as I am not fully satisfied with your comment on your definition of "finite precision":

If I understand your comment correctly, you imply that results like Theorem 4, which are not the "unbounded counting case" are also valid if we assume "full" finite precision, meaning an overall bounded number of bits for representing numerical values?
Thanks. We will be happy to cite this paper, and briefly discuss how star-free state tracking relates to probabilistic regular and context-free grammars. Our results on Dyck languages are particularly relevant in relation to the latter.
Given the formal nature of the paper’s title, it may be beneficial to reference the related paper available at https://arxiv.org/abs/1606.06737, which discusses formal language and the hidden Markov model. As the state-space model is a specific type of hidden Markov model, a brief discussion on the relationship between star-free state tracking, probabilistic regular grammar, and context-free grammar would be a valuable addition to the paper.