Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory
Authors: Nikola Zubic
Federico Soldà
Aurelio Sulser
Davide Scaramuzza
Venue: ICLR 2025 Poster (2025)
Keywords: theory
complexity theory
state space models
deep learning architectures
logic in computer science
Primary area: learning theory
TL;DR: We theoretically prove the shortcomings of current deep learning models with a specific focus on State Space Models.

Abstract: Despite their successes, deep learning models struggle with tasks requiring complex reasoning and function composition. We present a theoretical and empirical investigation into the limitations of Structured State Space Models (SSMs) and Transformers in such tasks. We prove that one-layer SSMs cannot efficiently perform function composition over large domains without impractically large state sizes, and even with Chain-of-Thought prompting, they require a number of steps that scale unfavorably with the complexity of the function composition. Also, the language of a finite-precision SSM is within the class of regular languages. Our experiments corroborate these theoretical findings. Evaluating models on tasks including various function composition settings, multi-digit multiplication, dynamic programming, and Einstein's puzzle, we find significant performance degradation even with advanced prompting techniques. Models often resort to shortcuts, leading to compounding errors. These findings highlight fundamental barriers within current deep learning architectures rooted in their computational capacities. We underscore the need for innovative solutions to transcend these constraints and achieve reliable multi-step reasoning and compositional task-solving, which is critical for advancing toward general artificial intelligence.

Published as a conference paper at ICLR 2025
LIMITS OF DEEP LEARNING: SEQUENCE MODELING THROUGH THE LENS OF COMPLEXITY THEORY
Nikola Zubić', Federico Soldá Aurelio Sulser Davide Scaramuzza'
Robotics and Perception Group,
University of Zurich, Switzerland
zubi cê fi .uz..e.... ch, sdavi de@ifi. cu
Algorithms and Optimization Group, ETH Zurich, Switzerland
federico so www.iaa.nneeeaaaaeee.e.mmaa st.z.ch
asulser(@stuentteethe
Equal contribution
ABSTRACT
Despite their successes, deep learning models struggle with tasks requiring com- plex reasoning and function composition. We present a theoretical and empirical investigation into the limitations of Structured State Space Models (SSMs) and Transformers in such tasks. We prove that one-layer SSMs cannot efficiently per- form function composition over large domains without impractically large state sizes, and even with Chain-of-Thouuhe prompting, they require a number of steps that scale unfavorably with the complexity of the function composition. Also, the language of finite-precision SSM is within the class of regular languages. Our experiments corroborate these theoretical findings. Evaluating models on tasks including various function composition settings, multi-digit multiplication, dynamic programming, and Einstein's puzzle, we find significant performance degradation even with advanced prompting techniques. Models often resort to shortcuts, leading to compounding errors. These findings highlight fundamental barriers within current deep learning architectures rooted in their computational capacities. We underscore the need for innovative solutions to transcend these con- straints and achieve reliable multi-step reasoning and compositional task-solving, which is critical for advancing toward general artificial intelligence.
INTRODUCTION
Deep learning has revolutionized numerous fields, achieving remarkable success in natural language
processing (OpenAl 2023 Google 2024 Touvron et al. (022)), computer vision (Nguyen et al. 2022
Zubié et al. 22024] Zhu et al. 2024), scientific computing (Merchant et al. 2023 Hansen et al. 2023
and autonomous systems (Kaulmann et al. 2023 Bousmalis et al. 2024). The pursuit general artificial intelligence
stands the new frontier, aiming develop Large Language Models (LLMs) capable of solving novel and complex tasks across diverse domains such as mathematics, coding, vision, medicine, law, and psychology, approaching human-level performance (Bubeck et al. 2023). Mastery of function composition is essential for this objective, as tasks like mathematical problem-solving (Li al. 2023), learning discrete algorithms (Thomm al. 2024 Veličković & Blundell, 2021), logical reasoning (Liu et al., (023b)), and dynamic programming (Dziri et al. 2023) are deeply compositional. However, despite impressive capabilities on various language tasks, deep learning models continue to struggle with tasks requiring complex reasoning over sequences. particularly those involving function composition and compositional reasoning (Peng et al., 2024
Dziri et al. 2023).
These tasks necessitate breaking down problems into simpler sub-problems and composing the solutions to these subtasks. Current Transformer models (Vaswani et al. 2017). including advanced ones like GPT-4, find it challenging to handle tasks demanding deep compositionality (Dziri et al. 2023). For instance, demonstrate that GPT-4 achieves only about 27% accuracy on basic tasks like b---iidt multiplication. One explanation for this limitation is the Transformer's 's inability to express simple state-tracking problems (Merrill & Sabharwal 2023a). Structured State Space Models

---

Published as a conference paper at ICLR 2025
(SSMs) (Gu et al.; 2022 Gu & Dao 2023) have been introduced alternative to Transformers,
aiming to achieve similar expressive power to Recurrent Neural Networks (RNNs) for handling problems that are naturally sequential and require state tracking. While SSMs have demonstrated impressive capabilities on various sequential tasks (Goel et al. 2022 Schiff' et al. 2024), they exhibit similar limitations to Transformer models in solving function composition problems. For the same 4- by-3-digit multiplication task, Jamba (Lieber et al. 2024), an SSM-Attention hybrid model, achieves only 17% accuracy.
Existing research has experimentally confirmed the inability of Transformers to perform function composition and compositional tasks (Dziri et al.] 2023] Zhao al. (024). leading issues such as mallucintions-rreppossss that are incompatible with training data and prompts. Complexity theory analysis further reveals that Transformers belong to a weak complexity class, logspace-unifon
TC (Merrill & Sabharwal 2023a), as do SSMs (Merrill et al. 2024), emphasizing their inherent limitations. While the impossibility of function composition for Transtormers has been theoretically studied (Peng et al., 2024). a similar theoretical understanding for SSMs remains lacking.
In this paper, we address this gap with two main contributions:
1. We provide theoretical framework using complexity theory to explain the limitations of SSMs in sequence modeling, particularly in their inability to perform function composition efficiently. We prove that one-layer SSMs cannot solve function composition problems over large domains without impractically large state size (Theorem [ Additionally, we show that even with Chain-of- Thain-tf-Thought prompting, SSMs require a polynomially growing number of steps to solve iterated function composition problems (Theorem (2)
2.
We extend our theoretical analysis to multi-layer SSMs, demonstrating that the computation of an L-layer SSM on a prompt of length N can be carried out using OL log N) bits of memory, positioning SSMs within the complexity class L (logarithmic space). This implies that SSMs cannot solve problems that are NL-complete unless L = NL, which is widely believed to be false (Peng al.) (024). We further discuss that SSMs share this limitation with Transformers, highlighting a fundamental barrier in current deep learning architectures (Theorem
Our critical insight is the formal proof that SSMs cannot solve iterated function composition problems without polynomially growing number Chain-of-Ti -h-ouhhttttht steps (Theorems multi-layer
I andd (2) and that even SSMs are limited to recognizing regular languages due to their essential equivalence to finite-state machines (Theorem 4 While CoT prompting can, to some extent, enable complex problem-solving by breaking down tasks into intermediate steps, it introduces trade-off between the model's state size and the number of input passes required, leading to increased resource demands, which is not optimal.
These findings underscore the need for innovative solutions beyond current deep learning paradigms to achieve reliable multi-step reasoning and compositional task-solving in practical applications.
2 EQUIVALENCE OF SSMS WITH OTHER DEEP LEARNING MODELS
Recent advancements in deep learning architectures have unveiled significant connections between SSMs and other prevalent models such as Linear Transformers. Notably, [ao Gui (2024) have demonstrated equivalence between Linear Transformers and SSMs, indicating that the computational processes of these models are fundamentally related. Moreover, SSMs can be trained like Convolu- tional Neural Networks (CNNs) and inferred as Recurrent Neural Networks (RNNs), leveraging the benefits of both convolutional and recurrent architectures. This duality allows SSMs to efficiently capture long-range dependencies like RNNs while benefiting from the parallelism during training characteristic of CNNs.
Additionally, Merrill al. (2024) have shown that SSMs and Transformers belong to the same computational complexity class, specifically logspace-uniform TC This alignment in computational capacity reinforces the notion that the limitations observed SSMs indicate inherent challenges within the broader landscape of deep learning models. Therefore, by focusing our theoretical and empirical analysis on SSMs, we effectively cover the representational capabilities of current deep- learning models, including Transformers and CNNs. This comprehensive coverage justifies our
2

---

Published as a conference paper at ICLR 2025
exploration of the limits of deep learning in sequence modeling through the lens of complexity theory. Our findings highlight the specific shortcomings of SSMs and shed light on the fundamental constraints of deep learning architectures in handling tasks that require reliable multi-step reasoning and compositional task-solving.
3 BACKGROUND
For two natural numbers n I m, we denote [n] = 1, 2..... n2 and [n,m] = = n + I...., m, with [0] [n, n - 1] = 0. We refer to the number of bits used in each computation computational precision p. Given two domains B, C, we denote by C the set of all functions from B to C.
Definition (SSM layer). Given an input sequence T1, Fn E Rmm an SSM layer L is defined in terms of a series of matrices A, Raxd B, E Rdxm. C2 E Rmxdd and D, E mu for t E [n].
C defines a sequence of states hi..... hn E IR as
h A B,
(1)
and outputs the sequence y1...., Un E m as
yt Cilu D
(2)
Generally, the matrices A, = Aax)), , B, B(xt), Ct = C(az), and D. Dax;) are functions of the input vector 2; for each t E [n]. In the special case when Ar, B,, Co and D. are independent from the input sequence æ1,... Tn. ,n,, we call L a linear SSM layer. Moreover, we call d the embedding dimension.
Remark: Although SSMs can be linked to streaming algorithms due to their limited hidden state, applying communication complexity to analyze their limitations in function composition involves intricate considerations unique to SSMs. No known streaming lower bound directly applies to our specific setting. Our analysis accounts for the particular architectural constraints of SSMs, providing better understanding of their capabilities than general streaming algorithms.
FUNCTION COMPOSITION REQUIRES WIDE ONE-LAYER MODELS
Our analysis considers one-layer SSMs to establish fundamental limitations in function composition tasks. The insights gained at the single-layer level highlight critical challenges that persist even in deeper architectures. The function composition problem has been introduced in (Peng et al. 2024) to provide a theoretical understanding of the causes of the hallucination of Transformer models. The aim is evaluate the model's 's capability to combine relational information in the data understand language, which is the core competence of large language models. Indeed to correctly answer questions like 'what is the birthday of Frédéric Chopin's 's father?' given the information that 'the father of Frédéric Chopin was Nicolas Chopin' and that 'Nicolas Chopin was born April 15, 1771', the model needs to able to compose the functions 'birthday-of" and 'father-of" (Peng et al., 2024]. (Guan al. 2024). Our analysis focuses on function compositions where the functions map elements from one finite, discrete domain to another, such as mapping individuals to their parents or birthdates. These functions operate over discrete sets, like persons and dates, and not over real-valued or continuous domains. Although this function composition task resembles a database join operation, it is important to note that our analysis focuses on how SSMs handle such compositions given natural language prompts. These prompts specify functions in an informal and potentially incomplete manner, lacking the full intensional knowledge present in formal database schemas. We aim to assess the model's s ability to perform reasoning over such natural language prompts despite their potential incompleteness.
Next, we give a precise formulation of the function composition problem due to (Peng et al. 2024). Consider two functions, mapping a domain A to a domain B, and f mapping B another domain C. These functions will be described in prompt X. The N tokens of X are divided into four parts:
1. the zeroth part describes the argument x E A,
2. the first part describes the function through |A] sentences in simple, unambiguous language separated by punctuation, e.g., 'the father of Frédéric Chopin is Nicolas Chopin',
3

---

Published as a conference paper at ICLR 2025
3. the second part consists of [B] sentences describing the function f, e.g., 'the birthday of Nicolas Chopin is April 15, 1771',
4. the third part is the query question asking for the value of f((())).
In this section, we discuss the theoretical limitations of SSMs for solving the function composition problem. In our analysis, the concept of domain size is crucial. While we primarily consider discrete domains, such finite sets like [n] {1,2. ..... n). it is important to discuss what domain size means in other contexts. For continuous domains like the interval [1. n). representing general functions would require infinitely many bits, making function composition intractable for models like SSMs and Transformers. Therefore, in practical settings, the maximum meaningful domain size is constrained by the total number of tokens and the prompt length, as the model's input capacity is limited. In our composition tasks, the functions are described within the prompt, so the prompt length effectively serves as an upper bound on the domain size.
Theorem 1. Consider function composition problem with input domain size |A| = |B| = n and an SSM layer L with embedding dimension d and computation precision p. Let n log n nannn-dd +d Z O, then the probability that L answers the query incorrectly is at least R/(3n log n) if f is sampled uniformly at random from C
The proof is based on reduction from famous problem in communication complexity (Peng et al., 2024). (Yoo 1979). Additional background on Communication Complexity and relevant problem classes be seen in the Appendix A We have three agents dubbed Faye, Grace, and Xavier. We assume that the agents have unbounded computational capabilities but, the only communication allowed is from Faye and Grace Xavier. Faye knows function f : [n] [r]] and the argument x E [n). Grace knows a function g [n] + [n]] and the argument x, while Xavier only knows the
argument E [n]. The goal is for Xavier to compute the value of f(]())), minimizing the total
number of bits communicated from Faye to Xavier and from Grace to Xavier.
We report lemma from (Peng al. 2024). which gives hardness result for the abovementioned problem.
Lemma (Lemmal from (Peng et 2024)). Consider the problem described above: fewer than
n log bits are communicated by Faye to Xavier, then Xavier cannot know the value f f(((z). In particular, if only n log R bits are communicated for some R 2 O, then the probability that the composition is computed incorrectly is at least R/(3n log n)) if is sampled uniformly at random from CB.
Now, we prove the theorem based on the Lemma above.
Proof of Theorem 7 To establish the bound on g. we give a reduction of the communication problem above the function composition problem. Let L be an SSM layer that can solve the function composition problem with probability 4.
Suppose we have Faye, Grace, and Xavier as in the settings above, and Xavier wants find the value [g(()). We construct the following prompt: the zeroth token æn is 'the argument of the function x², for i [1, n| let æ; be the token 'g applied i is g(i)", where the information is provided by Grace, and for i E [n + 1, 2n] let o; be the token string 'f applied to i is f()), where the information provided by Faye. Xavier provides the last token string 22n-1 'what is the value of f((())) Since the SSM layer L can solve the composition task with probability we have that:
y2n++1
C2n+ h22+11 + D2n4 D2m4142244 f((())
with probability g.
But this allows us to construct the following communication protocol. Since Grace knows y and the argument she knows the values of x; for i E [0,n] and she iteratively computes:
h A,h;-1 + Bæ,,
and then sends hn Xavier. On the other hand, Faye knows and hence the values of w; for i E [n + 1, 2n), she computes the matrix:
2n
Aj.
(5)
j=n+1
4

---

Published as a conference paper at ICLR 2025
then the vector:
2n b
Σ
II
A
B
(6)
f=++1
and she sends them Xavier. this point, Xavier computes:
h2n+1 A2n+1 (A h, + b) B2n+1 B2n+1
(7)
and finds the value of f[((x)) with probability q by computing y2n+1 C2n+1 -22n +2n4 22 The total number of bits of communication between Faye and Xavier is (d + +d) p. By Lemma follows that q S R/(3n logn).
Our theoretical results in Theorem | highhlight that SSMs, like other deep neural networks, approxi- mate functions rather than perform symbolic reasoning. Specifically, the probability bound indicates that if we attempt to compose functions over domains of size n with an SSM of embedding dimension and computational precision p such that (d2 + d)p n log n/2, the model will output the incorrect result with a probability of at least 1/6. To achieve a high probability of correctness (e.g., 99%), (d2 d)p must be significantly larger than n logn//2 n//2. This establishes a strong lower bound on the model's 's width, demonstrating that to accurately perform function composition over large domains, the model's capacity must increase substantially.
While Theorem I adddresess the limitations of one-layer SSMs, a natural question arises: Can deeper SSMs overcome these limitations? We conjecture that any SSM with a constant number of layers would still be unable to resolve the iterated composition task (as formalized in Chain-of-Thouge section 5). This is because accurately communicating token embeddings between layers becomes increasingly challenging necessary information across layers suggests that simply increasing the number of layers without a corresponding increase in model capacity does address the fundamental limitations identified.
the depth grows. The difficulty in preserving and transmitting the
MANY THOUGHT STEPS ARE NEEDED
chain of thought (CoT) is a series of intermediate natural language reasoning steps that lead to the final output. In this section, focus language models that can generate similar chain of thought- a coherent series of intermediate reasoning steps that lead the final answer for a problem. In (Wei et al. 2022), it was observed that CoT can mitigate the issue of hallucinations by encouraging the LLM to generate prompts that break down the task into smaller steps, eventually leading to the correct answer. In this section, prove that, in general, many CoT steps needed break down compositional tasks.
We start the discussion with the formal definition of SSM with & CoT steps. It adapts the definition for the Transformer model of (Merrill & Sabharwal 2024) to the case of SSMs.
Definition 2 (SSM with CoT). Let Φ (RR - Rmm he a function mapping a prefix of tokens to new token. The function & is parametrized by an SSM layer L.
Given an input sequence æı, .2,..., E. E Rm, we call:
Φx( Ø2,-... ,2,...,,n.) = 0b (2 ...,..., ra) ((0x-1(0)) D2. En,) 00, 002
Dnn):
where &1 (x1, D2...., In) ) = p(x .2...., xn) and denotes concatenation, the output of the SSM layer L with & CoT-steps.
In this section, we want prove that while this procedure could help SSM layers with compositional tasks, it might require many CoT steps to be effective. In particular, we focus on the iterated function composition problem and show lower bound on the number of CoT steps needed by SSM layer to solve this problem correctly.
In the iterated function composition problem and we need to calculate f f2(f(())) ...)) for E [n]. Here we restrict to the case when fi = f2 = fú, we define (x) ) := f(f(... (f((...(fo fx))), and we call this i-iteerted function composition problem.
given k functions f2, f2. .... [n] [n].
5

---

Published as a conference paper at ICLR 2025
Theorem 2. Consider iterated composition problem with domain size n, computation precision p. and embedding dimension d. An SSM layer requires Q 1 CoT steps for answering correctly iterated function composition prompis.
dy
The proof relies on reducing the iterated function composition problem from the pointer chasing problem (Papadimitriou & Sipser 1982), classical problem in communication complexity. In the k-steps pointer chasing problem, we have two agents dubbed Alice and Bob; Alice knows a function fA [n] > [n] and Bob knows function fB [n] r [n]. We then define the pointers:
21 =1 22 = fa(2)), 23 = fB<2))
24 = fa(zs), 25 = fz((2))
The communication proceeds for 2k rounds, with Alice starting. The goal is for Bob to output the binary value of 22k+2 mod 2. Following, we prove that an SSM layer with R CoT steps solving the iterated function composition problem pointer chasing problem where the number of transmitted bits scales with R. The next fundamental Lemma in communication complexity gives lower bound on the number of bits that need to be communicated in any such communication protocol, thus allowing the lower bound to be derived on the CoT steps.
be used design communication protocol for the
Lemma (Theorem 1.1 (Yehudayoff 2020 ) Any randomized protocol for the k-steps pointer chas- ing problem with error probability 1/3 under the uniform distribution must involve the transmission of at least n. n (2000k) - 2k log n bits.
Before we begin with the actual proof, let us introduce some notation. We note that on is a string of tokens of IR" Moreover, to compute the new token Φ( (æ), ........ Fn,, 21, Ø2, 2n,) the SSM layer L computes n + (k-1) 1) hidden states. We denote the i-th hidden state by
).
Proof of Theorem The proof is similar to the proof of Theorem 2 in (Peng et al. 2024). We reduce the pointer chasing problem to the iterated composition problem with CoT prompts. In particular, we show that if the SSM L can solve the k-iterated function composition problem with R CoT steps, then we can construct a protocol solving the (k - 1)-stess pointer chasing problem using 2 Rdlp bits of communication.
Fix a (I: 1) sttpss pointer chasing problem for the function fA. fB [n] +> [n]. Define the function f: [2m] + [2n] as:
(f(() +n, E [1,n]: (f ie [n 1m2
f(i)
(8)
We point out that (i) (fn fa) (k). Consider the k-iterated function composition problem for f and suppose that there exists an SSM L that solves it using R CoT steps.
We construct the following prompt: for i [1, n] let æ; be the token 'f applied to i is f()', where the information f(i) is provided by Alice, and for E [n + 1, 2n] let æ;; the token string 'f applied is f(i). where the information (i) is provided by Bob. The last token string #2a41 is given by 'what is the value of (() applied x Since the SSM layer L can solve the k-iterated function composition task with R CoT steps, we have that ( F2n) is the right answer for (*))). We will use this fact to construct communication protocol transmitting at most 2 Rdp bits. The communication protocol lasts for It rounds.
In the r-th round Alice computes 6r 1#1 L2n) from Φ ( ........ 2zn) (where @0(21.... ) is the empty string of tokens) and æi...., Fn and communicates it with Bob. & Bob on the other hand computes (2 F2n) from Φr. (ZI.... . Fzn) and In+1..... 32n
and transmits it to Alice. In each iteration, at most dp bits are communicated from Alice to Bob and from Bob to Alice.
After R rounds, Bob knows the value of dn( ). By hypothesis, this is the solution to the (k: 1)-steps pointer chasing problem. Notice that the total number of bits communicated by the protocol is 2ddp. In conclusion, fix k
+ 1 and by Lemma get that log
100
2 2R 2 n/ (2000k) 2k log n which gives R > 100 dp

---

Published as a conference paper at ICLR 2025
6 SSMS ARE LIMITED TO REGULAR LANGUAGES
In Peng et al. (024)). it is suggested to analyze the computational capability of LLMs on the compu- tational problems below. The empirical compositional tasks studied later sections of multi-digit integers, dynamic programming. and logic puzzles such as "Einstein's 's Riddle" can be expressed in terms of these computational problems (Peng al. (2024).
Circuit evaluation: Given the description of a circuit with gates, which can be either Boolean or arithmetic operations, as well as the values of all input gates of the circuit, evaluate the output(s) of the circuit. Multiplying decimal integers with multiple digits is an example of such a circuit.
Derivability: Given a finite domain S and a relation D S S. For given initial set I S S and a final set F C S. answer the question whether there are elements d1, .2,............................. ag S such that (a) ag E I, (b) dg E F. and (c) for all j such that < j S k, ,,) E D.
Logical reasoning: Logic puzzles like 'Einstein's ' Riddle' can typically be formulated as satisfiability (or SAT) instances. This problem NP-complete. However, most common- sense reasoning can be expressed by one of the three tractable exceptional cases of SAT: 2-SAT, Horn SAT, and Mod 2 SAT.
In Peng et al. 2024), it was noted that Derivability and 2-SAT are NL-complete, while Horn SAT and Circuit Evaluation are P-complete problems. Since the log-precision Transformer model lies in the complexity class log-uniform TC C L (Merrill & Sabharwal 2023b), these problems cannot be solved by a log-precision Transformer model provided NL 7 (which is a widely believed hypothesis in computational complexity). For Mod 2 SAT, the result is valid provided the weaker statement L 전 Mod 2 L. For Horn SAT and Circuit Evaluation, the result holds unless the stronger statement L P holds. Very recently, in Merrill et al. 2024), it was established that log- reg-precision linear and S6-SSMs (Gu & Dao 2023) are also part of the complexity class log-uniform TC', which yields the following theorem similar to the case of Transformers.
Theorem 3. The problems of Derivability and 2-SAT cannot be solved by log log-precision linear or S6-SSMs provided L + NL. For Mod 2 SAT, the result is valid provided the weaker statement * Mod 2 L holds. For Horn SAT and Circuit Evaluation, the result holds unless the stronger statement L P holds.
So far, we have explored SSMs' computational capabilities and limitations in various settings. In particular, SSMs face fundamental challenges when handling tasks requiring complex reasoning or computations beyond their inherent architectural constraints. Building on these insights, we now examine the impact of finite precision arithmetic on the computational power of SSMs. In practical implementations, SSMs operate with finite precision due to hardware constraints, typically using fixed- point or floating-point representations with a limited number of bits. This finite precision restricts the range and granularity of values that the model's parameters and hidden states represent. Let us denote by S the vectors that the hidden states can take. Consequently, it is reasonable to assume that an SSM does not embed store all the information provided during training. Instead, it must extract and retain only a subset of relevant information within a memory of much smaller capacity than the input.
Since SSMs have a fixed hidden dimension and operate with finite precision, the set S is finite. This finiteness imposes significant restrictions on the types of languages that SSMs can compute or recognize. To formalize this limitation, we introduce the following definition:
Definition 3. Given a
SSM, we say the SSM accepts an input sequence II...., I if the hidden state ha+1 1 # O. We call the of accepted inpul sequences the language of the SSM.
The following theorem relates the computational power of a finite precision SSM to Finite-State Machine (FSM).
Theorem 4. The language of a fimite-precision SSM is within the class of regular languages.
Proof. We construct the Finite-Statt State Machine M = (Q, 8, qo. F), where:
1. the set of states Q is the set of all possible vectors ʃ.
2. the finite input alphabet E is as well S,
7

---

Published as a conference paper at ICLR 2025
3. the transition function ó: Q Σ² Q is defined by the SSM's state update equations, i.e., 6( h,, x) = A(x)h + B(x)x
4. is the initial state corresponding to the initial hidden state ho,
5. F Q \ (0) is the set of accepting states.
Since the SSM has finite precision, the set V is finite, and this defines a valid FSM. is immediate that the FSM models the transitions the SSM and accepts the same language.
This result relates the computational power of SSMs to FSMs. Consequently, under finite precision constraints, SSMs cannot recognize languages beyond regular languages. Regarding computational limitations, tasks requiring computational models with greater expressive power, such as context-free grammars or context-sensitiee grammars, cannot be efficiently solved by SSMs with finite precision. Examples of such tasks include recognizing balanced parentheses, detecting palindromic sequences, and performing more complex logical inference that necessitates memory beyond finite states.
These limitations are significant because they highlight the boundaries of what SSMs can achieve in practical settings. Regarding practical considerations, since real-world implementations of SSMs operate on hardware with finite memory and finite precision arithmetic, these theoretical limitations directly apply to SSMs used in actual applications. Therefore, when designing systems for tasks that require processing beyond regular languages, it becomes clear that SSMs with finite precision do not suffice, and alternative architectures computational mechanisms need to be considered to overcome these inherent constraints.
7 EXPERIMENTS
Our theoretical results suggest that SSMs inherently struggle with function composition and multi- step reasoning tasks due to their architectural limitations. To validate these findings, we empirically assess SSMs' performance practical tasks requiring these capabilities.
We evaluate the inability of various sequence models to address function composition tasks by examin- ing three axes of composition: spatial, temporal, and relational (Appendix [B.I). This evaluation uses four datasets designed to test function composition. Subsequently, we proceed to compositional tasks involving multi-digit multiplication, dynamic programming, and Einstein's 's puzzle. We investigate the effects of Chain-of-Thoon Thought (CoT) prompting (Appendix B.2) and conduct thorough error analysis understand the failure points and underlying reasons for the erroneous behavior (Appendix B.3).
We conducted GPT experiments using the ChatGPT API (OpenAl 2023) and performed all exper- iments with the GPT-4 model of June 2024, while other models were evaluated on machines equipped with 2x NVIDIA A100 80 GB GPUs. We used Jamba version 1. Unless otherwise specified, each task evaluated three times with 500 test samples per evaluation to ensure consistency and minimize variance. All other experimental details, including prompts and additional results, are provided in the Appendix.
8 RELATED WORK
Limitations in Function Composition and Reasoning Recent studies have underscored the limitations of deep learning models, particularly Transformers. handling tasks requiring deep compositionality and multi-step reasoning (Peng et al. 2024 Dziri et al.] 2023). These tasks are crucial in applications like mathematical problem-solving (Li et al. 2023), algorithm learning (Thomm et al., 2024 VVelčkovié & Blundell 2021), logical reasoning (Liu et al. (023b), and dynamic programming (Dziri et al. 2023). Despite their capabilities, Transformers have been shown to struggle with function composition, which is essential for understanding relational information in data (Guan et al. 2024).
Research has highlighted architectural and training limitations that prevent these models from maintaining accuracy over multiple reasoning steps, leading to issues like hallucinations and reasoning emorr (Merrill & Sabharwal 2023a Zhao et al. 2023). Studies by Merrill al. (2024) and Peng et al.
8

---

Published as a conference paper at ICLR 2025
(2024) have identified that both Transformers and SSMs belong to weak complexity classes, such as logspace-uniforn TC", which limits their computational abilities. However, prior work primarily focused on Transformers, with SSMs not thoroughly investigated theoretically and empirically concerning their ability perform function composition and compositional tasks. Our contribution fills this gap by providing a comprchensive theoretical framework and empirical analysis specific to SSMs.
Chain-of- Shain-o--Though Thought Prompting The Chain-of-Thoughl (Co'T) prompting method has been proposed to improve reasoning capabilities in large language models by breaking down complex tasks into smaller, intermediate steps (Wei et al. 2022). CoT prompting aims mitigate issues like hallucina- tions and enhance multi-step reasoning by encouraging models to generate intermediate reasoning steps. While CoT has shown promise in specific contexts, recent research indicates that even with CoT prompting, current models remain inadequate for solving deeply compositional tasks (Merrill Sabharwal 2023a Liu et al., 2023a). Our work supports these findings, demonstrating that CoT prompting does not overcome the fundamental computational limitations SSMs and Transformers in tasks requiring complex reasoning.
While advanced methods like tree search algorithms Trinh et al. 2024 Polu Sutskever 2020 Lample et al. 2022) and self-correction techniques (Wang al. [2024] Kumar et al. (2024) have been proposed to improve reasoning by integrating external mechanisms, our work focuses on the inherent computational limitations of SSMs and Transformers when used without such augmentations. These external engines can mitigate some limitations by leveraging additional resources, but they do not address the core architectural constraints we have identified.
Expressive Power and Complexity of Neural Networks A growing body of work is exploring the expressive power of neural network architectures and their limitations from a computational complex- ity perspective. |Weiss et al. (0118) and Siegelmann & Sontag 1992] examined the capabilities of recurrent neural networks in relation to Turing machines. Pérezz et al. (2019) investigated the Turing completeness of Transformers under certain conditions.
More recently, Merrill et al. 2020) analyzed the relationship between network depth, parameter size, and computational expressivity. Bhattamishra al. (2020) explored the computational limitations of Transformers concerning formal languages. Our work contributes to this line of research by analyzing SSMs within the framework of computational complexity, specifically their placement within the class L and implications for their reasoning capabilities.
Alternative Approaches to Complex Reasoning Given the limitations of current architectures, researchers have explored alternative approaches to enhance models' reasoning abilities. Methods include integrating external memory modules (Graves et al.) (2066), incorporating symbolic reasoning components (Gaunt et al. 2017). and developing neuro-symbolic models (Dai et al. 2019). These approaches aim to combine the strengths of neural networks with symbolic computation to overcome the shortcomings in tasks requiring complex, multi-step reasoning. Our findings underscore the necessity for such innovative solutions, suggesting that overcoming the fundamental limitations identified requires moving beyond traditional deep learning paradigms.
CONCLUSION
In this work, we have demonstrated both theoretically and empirically that Structured State Space Models (SSMs) and Transformers face fundamental limitations performing function composition and complex reasoning tasks. Our theoretical analysis shows that overcoming these limitations would require architectures beyond finite-state machines. SSMs with fixed hidden dimensions and layers are equivalent finite-state machines and thus limited to regular languages (Theorem 4.. This limitation explains their inability to handle tasks that require computational power beyond regular languages, such context-free -ree languages or problems that NL-complete.
Our empirical evaluations confirm these findings, revealing significant performance degradation as task complexity increases, even when employing advanced prompting techniques. Models often resort to shortcuts, leading to errors in multi-step reasoning processes. These results highlight that current deep learning architectures fundamentally limited in their ability perform reliable

---

Published as a conference paper at ICLR 2025
multi-step reasoning and compositional task-solving due their architectural constraints. This underscores the necessity for innovative architectural solutions or computational frameworks that can handle such tasks more efficiently. Future research should explore new directions, such integrating symbolic reasoning components, improving memory and state-tracking capabilities, or developing hybrid models that transcend the limitations of existing architectures. Addressing these challenges is crucial for advancing toward general artificial intelligence capable of sophisticated reasoning and problem-solving across diverse domains.
10 ACKNOWLEDGMENT
This work supported by the European Research Council (ERC) under grant agreement No. 864042 (AGILEFLIGHT).
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Samira Abnar, Omid Saremi, Laurent Dinh, Shantel Wilson, Miguel Angel Bautista, Chen Huang, Vimal Thilak, Etai Littwin, Jiatao Gu, Josh Susskind, and Samy Bengio. Adaptivity and modularity for efficient generalization task complexity, 2023.
S. Bhattamishra, Arkil Patel, and Navin Goyal. implications in sequence modeling. In Conference on Computational Natural Language Learning, 2020.
On the computational power of transformers and its
Konstantinos Bousmalis, Giulia Vezzani, Dushyant Rao, Coline Manon Devin, Alex X. Lee, Maria Bauza Villalonga, Todor Davehev, Yuxiang Zhou, Agrim Gupta, Akhil Raju, Antoine Laurens, Claudio Fantacci, Valentin Dalibard, Martina Zambelli, Murilo Fernandes Martins, Rugile Pevceviciute, Michiel Blokzijl, Misha Denil, Nathan Batchelor, Thomas Lampe, Emilio Parisotto, Konrad Zolna, Scott Reed, Sergio Gómez Colmenarejo, Jonathan Scholz, Abbas Abdol- maleki, Oliver Groth, Jean- Baptistt Regli, Oleg Sushkov, Thomas Rothörl, Jose Enrique Chen, Yusuf Aytar, David Barker, Joy Ortiz, Martin Riedmiller, Jost Tobias Springenberg, Raia Hadsell, Francesco Nori, and Nicolas Heess. Robocat: A self-improving generalist agent for robotic manipulation. Trans. Mach. Learn. Res., 2024.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303. 12712 2023.
Zihang Dai, Zhilin Yang, Yiming Yang. Jaime G. Carbonell, Quoe Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond fixed-length context. In Annu. Meet. Assoc. Comput. Linguist., 2019.
Tri Dao and Albert Gu. Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality. In Int. Conf. Mach. Learn., 2024.
Leonardo de Moura and Nikolaj Bjørner. 73: An efficient smt solver. In C. R. Ramakrishnan and Jakob Rehof (eds.), Tools and Algorithms for the Construction and Analysis of Systems, 2008.
Mengnan Du, Fengxiang He, Na Zou, Dacheng Tao, and Xia Hu. Shortcut learning of large language models in natural language understanding. Commun. ACM, 2022. URL https
Nouha Dziri, Ximing Lu, Melanie Selar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. Faith and fate: Limits of transformers compositionality. In NeurIPS, 2023. URL
Fkckkr3ya8
Daniel Y. Fu, Tri Dao, Khaled K. Saab, Armin W. Thomas, Atri Rudra, and Christopher Ré. Hungry Hungry Hippos: Towards language modeling with state space models. In ICLR, 2023.
Alexander L. Gaunt, Mare Brockschmidt, Nate Kushman, and Daniel Tarlow. Differentiable programs with neural libraries. In Int. Conf. Mach. Learn., 2017.
Robert Geirhos, föm--Herikk Jacobsen, Claudio Michaclis, Richard S. Zemel, Wieland Brendel, Matthias Bethge, and Felix Wichmann. Shorteut learning in deep neural networks. Nature Mach. Intell., 2020.
Karan Goel, Albert Gu, Chris Donahue, and Christopher Ré. It's raw! audio generation with state-space models. Int. Conf. Mach. Learn., 2022.
Gemini Team Google. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. ArXiv, 0aw//2403.055300 2024. httph::p////// //apii semanticschoiar org/ forpusTD:2682271155
11

---

Published as a conference paper at ICLR 2025
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwinska, Sergio Gomez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John P. Agapiou, Adria Puigdomenech Badia, Karl Moritz Hermann, Yori Zwols, Georg Ostrovski, Adam Cain, Helen King, Christopher Summerfield, Phil Blunsom, Koray Kavukcuoglu, and Demis Hassabis. Hybrid computing using neural network with dynamic external memory. Nature, 2016.
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces, 2023.
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. In ICLR, 2022.
Xinyan Guan, Yanjiang Liu, Hongyu Lin, Yaojic Lu, Ben He, Xianpei Han, and Le Sun. Mitigating large language model hallucinations via autonomous knowledge graph-based retrofitting. In AAAI, 2024.
Derek Hansen, Danielle Maddix Robinson, Shima Alizadeh, Gaurav Gupta, and Michael Mahoney. Learning physical models that respect conservation laws. In Inf. Conf. Mach. Learn., 2023.
Elia Kaufmann, Leonard Bauersfeld, Antonio Loquercio, Matthias Müller, Vladlen Koltun, and Davide Scaramuzza. Champion-level drone racing using deep reinforcement learning. Na- ture, 2023. doi: 10. 10.1038//41586-023-064111 s41586 023 06419-4
URL httpps://do. /ttpss////6i.orr/001113333
Jon Kleinberg and Eva Tardos. Algorithm Design. Addison-Wesley Longman Publishing Co., Inc., USA, 2005, ISBN 0321295358.
Aviral Kumar, Vincent Zhuang, Rishabh Agarwal, Yi Su, John D. Co-Reyes, Avi Singh, Kate Baumli, Shariq Iqbal, Colton Bishop, Rebecca Roelofs, Lei M. Zhang, Kay McKinney, Disha Shrivastava, Cosmin Paduraru, George Tucker, Doina Precup, Feryal M. Behbahani, and Aleksandra Faust. Training language models to self-correct via reinforcement learning. ArXiv, 2024.
Guillaume Lample, Marie-Amee Lachaux. Thibaut Lavril, Xavier Martinet, Amaury Hayat, Gabriel Ebner, Aurelien Rodriguez, and Timothée Lacroix. Hypertree proof search for neural theorem proving. ArXiv, abs/2205.1 1491, 2022.
Guohao Li, Hasan Abed Al Kader Hammoud, Hani Itani, Dmitrii Khizbullin, and Bernard Ghanem. CAMEL: Communicative agents for "mind" exploration of large language model society. In NeurlPS, 2023. URL. htt.:tttss///peeeeee/////e wwwpoopeeevvvieeeeeeeeeee net www.w//weneeeemmmmmmm// d=3 3
Opher Lieber, Barak Lenz, Hofit Bata, Gal Cohen, Jhonathan Osin, Itay Dalmedigos, Erez Safahi, Shaked Meirom, Yonatan Belinkov, Shai Shalev-Shwartz, Omri Abend, Raz Alon, Tomer Asida, Amir Bergman, Roman Glozman, Michael Gokhman, Avashalom Manevich, Nir Ratner, Noam Rozen, Erez Shwartz, Mor Zusman, and Yoav Shoham. Jamba: hybrid transformer-mamba language model, 2024.
Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. ICLR, 2023a. doi: 10.48550/arXxv.2220.. 10749. URL https
//openreview.co wwt..nttoooommdddeeeeeeee
Hanmeng Liu, Ruoxi Ning. Zhiyang Teng. Jian Liu, Qiji Zhou, and Yuexin Zhang. Evaluating the
logical reasoning ability of chatgpt and gpt-4. ArXiv, abs/2304.03439, 2023b. URL https
//api. www.ssmmttticcocaacacae wwt.laarrrrrr/ooousssa
:
Pan Lu, Baolin Peng, Hao Cheng. Michel Galley, Kai-Wei Chang, Ying Nian Wu, Song-Chun and Jianfeng Gao. Chameleon: Plug-and-play compositional reasoning with large language models. In NewrlPS, 2023.
Chun Zhu,
Amil Merchant, Simon Batzner, Samuel S. Schoenholz, Muratahan Aykol, Gowoon Cheon, and Ekin Dogus Cubuk. Scaling deep learning for matcrials discovery. Nature, 2023, doi: 1038/ 441586-023-06735--1 URL doi org 10. 1038 8410//4110 /415/41118855 18661586-1100 023 -2223---733---
William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log precisciioon transformers. Trans. Assoc. Comput. Linguist., 2023a. doi: 16.1/6// a 00562. URL https
7/aclantho ogy. org.oorg/2023 tast-alllle 11.1
12

---

Published as a conference paper at ICLR 2025
William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log rog-precision transformers. Transactions of the Association for Computational Linguistics, 11:331-545, 2023b.
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought, 2024.
William Merrill, Vivek Ramanujan, Yoav Goldberg, Roy Schwartz, and Noah A. Smith. Effects of parameter norm growth during transformer training: Inductive bias from gradient descent. In Proc. Conf. Empirical Methods in Nat. Lang. Process., 2020.
William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in state-space models, 2024.
Roshanak Mirzaee and Parisa Kordjamshidi. Transfer learning with synthetic corpora for spatial role labeling and reasoning. In Proc. Conf. Empirical Methods Nat. Lang. Process. Association for Computational Linguistics, 2022.
Eric Nguyen, Karan Goel, Albert Gu, Gordon Downs, Preey Shah, Tri Dao, Stephen Baccus, and Christopher Ré. $4nd: Modeling images and videos as multidimensional signals with state spaces. In NeurlPS, 2022.
OpenAl. Gpt-4 technical report, 2023.
Christos H. Papadimitriou and Michael Sipser. Communication complexity. In Proc. Annu. ACM Symp. Theory Comput. Association for Computing Machinery, 1982. doi: 10. 45/800070.800211 URL https:://oi.orgg /10. 1145/ 0005/800070.00 802192
Binghui Peng, Srini Narayanan, and Christos Papadimitriou. On limitations of the transformer architecture, 2024.
Jorge Pérez, Javier Marinkovic, and Pablo Barceló. On the turing completeness of modern neural network architectures. ICLR, 2019.
Stanislas Polu and Ilya Sutskever. Generative language modeling for automated theorem proving. ArXiv, abbs/2009003334) 2020.
Patrick Prosser. Hybrid algorithms for the constraint satisfaction problem. Comput. Intell., 1993. URL httthhttss://pppp www.nt. ott.aaatrr...p................o. otspr//a....ccooooooooooooopopp. 36951414
Yair Schiff, Chia-Hsiang Kao, Aaron Gokaslan, Tri Dao, Albert Gu, and Volodymyr Kuleshov. Caduceus: Bi-directional equivariant long-range dna sequence modeling, 2024.
Hava T. Siegelmann and Eduardo Sontag. On the computational power of neural nets. In Annual Conference Computational Learning Theory, 1992.
Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung. Aakanksha Chowdhery, Quoc V Le, Ed H Chi, Denny Zhou, and Jason Wei. Challenging big-bench tasks and whether chain-of-thougeee can solve them. arXiv preprint arXiv:2210.09221, 2022.
Ruixiang Tang, Dehan Kong, Lo li Huang, and Hui Xue. Large language models can be lazy learners: Analyze shortcuts in in-context learning. In Annu. Meet. Assoc. Comput. Linguist., 2023. URL
Jonathan Thomm, Aleksandar Terzic, Geethan Karunaratne, Giacomo Camposampiero. Bernhard Schölkopf, and Abbas Rahimi. Limits of transformer language models on learning algorithmic compositions, 2024.
Shivin Thukral, Kunal Kukreja, and Christian Kavouras. Probing language models for understand- ing of temporal expressions. In BlackboxNLP Workshop Analyzing and Interpreting Neu- ral Nenworks for NLP, 2021. BtRh:ttps: /app..app///////////.aaa www.nticscho...o........ org/CorpusiDt
238259493
13

---

Published as a conference paper at ICLR 2025
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix. Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models. ArXiv, 2023.
Trieu Trinh, Yuhuai Wu, Quoe Le, He He, and Thang Luong. Solving olympiad geometry without human demonstrations. Nature, 2024. doi: 1111038/411586-023-6674444
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. NeurIPS, 2017.
Petar Veličković and Charles Blundell. Neural algorithmic reasoning. Patterns, 2021.
Yifei Wang, Yuyang Wu, Zeming Wei, Stefanie Jegelka, and Yisen Wang. A theoretical understanding of self-correction through in-context alignment. In Int. Conf. Mach. Learn., 2024.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. tfahh-of- prompting elicits reasoning large language models. In NeurlPS, 2022.
Gail Weiss, Yoav Goldberg, and Eran Yahav. On the practical computational power of finite precision mns for language recognition. Anmu. Meet. Assoc. Comput. Linguist., 2018.
Sohee Yang, Elena Gribovskaya, Nora Kassner, Mor Geva, and Sebastian Riedel. Do large language models latently perform multi-hop reasoning? ArXiv, 2024.
Andrew Chi-Chih Yao. Some complexity questions related to distributive compating(preliminary report). In Proc. Annu ACM Symp. Theory Comput. Association for Computing Machinery, 1979. doi: 10.1145/800135. 8044444 URL http:///oo...oor/0001111///00030
http://oiiiooo 1ttp:/10..111580001000
804414
Amir Yehudayoff. Pointer chasing via triangular discrimination. Comb. Probab. Comput.. 2020.
Chiyuan Zhang, Maithra Raghu, Jon Kleinberg, and Samy Bengio. Pointer value retrieval: A new benchmark for understanding the limits of neural network generalization, 2022.
Jun Zhao, Jingqi Tong, Yurong Mou, Ming Zhang, Qi Zhang, and Xuanjing Huang. Exploring the compositional deficiency of large language models in mathematical reasoning, 2024.
Lin Zhao, Lu Zhang. Zihao Wu, Yuzhong Chen, Haixing Dai, Xiaowei Yu, Zhengliang Liu, Tuo Zhang, Xintao Hu, Xi Jiang, Xiang Li, Dajiang Zhu, Dinggang Shen, and Tianming Liu. When brain-inspired ai meets agi. Meta Meta-Radiology. 2023. ISSN 2950-1628.
L Lianghui Zhu, Bencheng Liao, Qian Zhang, Xinlong Wang, Wenyu Liu, and Xinggang Wang. Vision mamba: Efficient visual representation learning with bidirectional state space model. arXiv preprint arXiv:2401.09417, 2024.
Nikola Zubié, Mathias Gehrig, and Davide Scaramuzza. State space models event cameras. In Proceedings of the IEEF/CVF Conference Computer Vision and Pattern Recognition (CVPR), 2024.
14

---

Published as a conference paper at ICLR 2025
Appendices
Background on Communication Complexity and Computational Classes
16
Communication Complexity
16
A.2
Computational Complexity Classes
16
A.3
Key Problems and Their Complexity
17
B
Main Experiments
18
B.
Function composition and compositional tasks
18
B.2
CoTl experiments
20
B.3
Error analysis
20
B.4
Learning Algorithmic Compositions
22
Compositional Tasks Details
22
Multiplication
22
Einstein's Puzzle
22
Dynamic Programming
24
Details of CoT experiments
25
D.I Main CoT experiments
25
D.2 Performance of other models on multiplicttion and puzzle tasks
...........
26
D.3 Few-shot prompting multiplication results
26
Algorithmic Compositions
27
Prompts for SSM and Attention-based models for PEN task
................................
28
PEN generation code
30
E.3 PER Multi-generation code
31
15

---

Published as a conference paper at ICLR 2025
A BACKGROUND ON COMMUNICATION COMPLEXITY AND COMPUTATIONAL CLASSES
To provide solid foundation for our theoretical results, we offer an overview of key concepts in communication complexity and computational complexity theory. This background is essential for understanding the limitations of SSMs and other deep learning architectures sequence modeling tasks that require complex reasoning.
A.1 COMMUNICATION COMPLEXITY
Communication complexity studies the amount of communication required between two more parties to compute a function whose input is distributed among them. provides lower bounds on the communication needed for distributed computation.
Communication Protocols: communication protocol specifies the rules by which parties exchange messages compute function collaboratively. The primary goal is minimize the total number of bits exchanged.
Key Problems in Communication Complexity:
Function Composition Problem:
Two parties, Faye and Grace, hold functions f B C and g A - B, respectively, along with a common input x E A. Their goal is to compute ((((x)) with minimal communication
third party, Xavier. This problem models scenarios where composing functions over large domains requires significant communication, highlighting the challenges in function composition tasks for sequence models.
Pointer Chasing Problem: This involves two parties who alternately apply functions an initial input over several rounds. It is fundamental problem used to establish lower bounds in communication complexity. It demonstrates that certain computations inherently require substantial amount of communication, regardless of the protocol used.
Set Disjoininess Problem: Two parties each hold subset of universal set and wish to determine if their subsets intersect without revealing additional information. This problem is notable for having high communication complexity, serving basis for proving lower bounds in various computational models.
Communication complexity provides tools to prove theoretical limits on the capabilities of computational models, including neural networks. By reducing problems in communication complexity to tasks performed by sequence models, we can establish lower bounds on the resources required (e.g., hidden state size, number of layers) for these models perform certain computations. This approach helps in understanding why models like SSMs struggle with tasks requiring complex reasoning or function composition.
Relevance to Sequence Modeling:
A.2 COMPUTATIONAL COMPLEXITY CLASSES
Computational complexity theory classifies problems based on the resources required to solve them, such as time or memory space. Understanding these classes is crucial for characterizing the limitations of computational models.
Key Complexity Classes:
L (Logarithmic Space): The class of decision problems solvable by a deterministic Turing machine using logarithmic amount of memory space with respect to the input size. Problems in L are considered efficiently solvable with very limited memory.
NL (Nondeterministic Logarithmic Space): Consists of decision problems solvable by nondeterministic Turing machine using logarithmic space. NL is broader class than L, as nondeterminism allows guessing and verifying solutions using limited memory.
P (Polynomial Time): Contains decision problems solvable by deterministic Turing machine in polynomial time. It represents problems that are efficiently solvable in terms of time, without specific memory constraints.
16

---

Published as a conference paper at ICLR 2025
The class of languages recognizable by finite automata equivalently, by regular expressions. They are the simplest class in the Chomsky hierarchy and can be recognized using constant memory.
Regular Languages:
Context-Free Languages: Recognizable by pushdown automata, these languages can handle nested structures and require memory that grows with the input size.
TC (Constant Depth Threshold Circuits): class of problems solvable by constant- depth, polynomial-size circuits with threshold gates. These circuits can compute certain functions very efficiently in parallel.
Relationships Between Classes:
Regular Languages L NL CP
It's widely believed that these inclusions are strict (e.g., L + NL), meaning each class strictly contains the previous one.
Relevance to Sequence Modeling: By placing computational models within these complexity classes, we can formalize their computational power and limitations. For instance:
Finite-State Machines (FSMs): Equivalent models that recognize regular languages. They have a finite number of states and cannot handle tasks requiring memory that scales with input size.
Pushdown Automata: Recognize context-free languages and can handle nested or recursive structures due to their use of a stack.
SSMs and Transformers: Our analysis shows that SSMs with fixed hidden dimensions and layers equivalent FSMs, limiting them to regular languages. Similarly, Transformers have been shown to have limitations corresponding to the class TC or L under certain conditions.
Implications for SSMs: Understanding that SSMs are limited to regular languages explains why they struggle with tasks requiring more computational power, such as:
Function Composition: Requires the ability to maintain and manipulate information over long sequences, which exceeds the capabilities of finite-state models.
Complex Reasoning Tasks: Problems like multi-digit multiplication, logical puzzles, and dynamic programming necessitate memory and computational resources beyond what is available models limited to regular languages.
By grounding our analysis in communication complexity and computational complexity theory. we establish theoretical foundation for the limitations of SSMs. This background enables to formalize the challenges faced by sequence models in handling tasks that require computational resources beyond regular languages and logarithmic space.
A.3 KEY PROBLEMS AND THEIR COMPLEXITY
To further contextualize the limitations of SSMs, we briefly describe some computational problems and their associated complexity classes:
Derivability (NL-Complete): Given finite and relation, determine if there is sequence of elements satisfying certain conditions. This problem requires nondeterministic NL.
logarithmic space and cannot be solved by models limited to L unless
2-SAT (NL-Complete): A satisfiability problem where each clause has at most literals. It is solvable in polynomial time but is NL-complete, indicating it requires more than deterministic logarithmic space.
Horn SAT and Circuit Evaluation (P-Complete): Problems that hard any problem in P. Solving these efficiently would require polynomial time computation, beyond the capabilities of FSMs.
17

---

Published as a conference paper at ICLR 2025
Mod SAT (Beyond L):
Involves solving satisfiability problems modulo 2. Requires computational resources beyond deterministic logarithmic space.
Relevance to Our Work:
The inability of SSMs to solve these problems stems from their equivalence to stttte-state machines. Since FSMs cannot utilize memory that grows with input size, they inherently incapable of solving problems that require maintaining and processing an unbounded amount of information. The limitations highlighted by these complexity classes and problems suggest that to handle complex reasoning tasks effectively, sequence models need architectures that go beyond finite-state state computations. This could involve models that can simulate pushdown automata or Turing machines, allowing them to recognize context-free frre languages or perform computations requiring more substantial memory resources.
B MAIN EXPERIMENTS
B. FUNCTION COMPOSITION AND COMPOSITIONAL TASKS
In the context of Large I Language Models (LLLss), compositional tasks differ from function com- position. Function composition fK (fk-1(... (f (z))) is a mathematical process where the output of one function serves as the input for another across multiple functions f1, f2..... ..... fk. Conversely, LLM compositional tasks involve breaking down complex inputs into simpler parts and integrating the results generate overall output. Examples include (i) combining linguistic elements to generate coherent text, (ii) solving multi-step reasoning problems, and (iii) decomposing complex tasks (e.g., multi-turn conversations, summarization) into manageable sub-tasks.
Solving compositional tasks necessitates the capability to perform function composition (Peng et al. 2024 Dziri al. 2023) and demands additional competencies such contextual understanding, multi-step reasoning, and the integration of diverse information types. A model's proficiency in function composition is a critical prerequisite for tackling complex compositional tasks (Lu al.) 2023). For instance, if an SSM-powered LLM cannot evaluate (9((),, it will be inadequate for tasks involving multi-step arithmetic or logical operations that depend on nested functions.
Composition tasks We begin with three fundamental composition tasks: spatial, temporal, and relationship compositions. These axes are crucial as they encapsulate core aspects comprehending and interacting with the world. Spatial composition entails integrating information about the positions and orientations of objects. Temporal composition involves reasoning over sequences and durations of events. Relationship composition focuses understanding the connections between entities, such as those in genealogy tree.
Number of Parameters We conducted experiments using Jamba (Lieber al. 2024) (joint Mamba and Attention) with 7B parameters, Mamba (Gu & Dao 2023) with 2.8B parameters, S4-H3 (Gu et al. 2022, Fu et al., (223)) with 2.7B parameters, GPT-4 (OpenAl 2023), and GPT-4o models. Qualitative results are presented in Fig. [ As illustrated in Fig. all models failed to answer questions across the three composition axes correctly.
Problem Sputial axis
Question: Rectungle to the west of the
Problem Tempural axis
Problem 3 Rehationshp axis
tagon. The trinngle the north of the
triangle the south of
Question: Anne the younger sister of Erwin, Erwin the elder brother of Daniel. Is Anne younger than Daniel?
Question: Alan is the son of Maroo, Joe is the son of Alan. Does Alan have any grankhildren?
square located relation the pentagon?
Janbaa Fest
Iamba: Yos X
Jamba: X
Mambu: Northeast
Mamsh::
Mamsh: X
GPT-4: Northeast X
GPT-4: Yes
GPT-4: No
GPT-4o: North X
GPI-4:: Yes
GPI-40: No
Northwest. /
Correct: Not enough information. /
Correct: Not enough information. V
Figure I: Qualitative example of zero-shot inference on prominent SSM and Attention-base models. None of the models successfully resolved the problems across any of the composition axes.
To quantitatively assess the limitations of models, including the latest GPT-4o (OpenAl 2023), in solving function composition tasks, we evaluate their performance on four datasets specifically designed to test these capabilities. Unless otherwise specified, each model is tested 500 samples.
18

---

Published as a conference paper at ICLR 2025
Composition datasets Math-QA dataset, derived from (Li al. 2023). includes 25 math topics. We focus on the first 100 samples from Algebra, Calculus, Combinatorics, Game Theory, and Trigonometry. Problems involve solving function compositions and temporal reasoning. BIG-Bench Hard (Suzgun et al. 2022) dataset features 250 Boolean expressions that the model must evaluate. In Temporal-NII (Thukral et al. 202T) dataset, each sample consists of premise (e.g.. "They got married on Saturday") and hypothesis (c.g., "They got married before Friday"). requiring the model determine if the relationship entailment, contradiction, or neutral. SpaRTUN (Mirzace & Kordjamshicl 2022) dataset is designed for spatial reasoning, and it includes stories describing the spatial positions of objects, followed by questions about the orientation of one object relative to another (e.g., left, right, inside, above).
GPT-4o
GPT-4
Jamba
Mamba
S4-113
GPT-4o
GPT-4
Jamba
Mamba
S4-H3
Math-QA
61 61.8%
51.0%%
42.2%%
35.0%
28.6%
Algebra
51%
47%
42%
369
25%
BIG-Bench Hard
56.8%
58. 1%%
78.2%
67.0%
60.6%
Calculus
50%
48%
41%
34%
Temporal NLI
79.4%
77.2%
69.8%
89.25%
54.6%
Combinatoriss
88%
70%
48%
38%
335%
SpaRTUN
80.8%
61.4%
50.8%
12.2%
35.2%
Game theory
309
40%
50%
11%
32%
Trigonomctty
30%
21%
Table 1: Performance Atlention, Attention baved models on various function composition tasks involving logical ex- pressions, temporal reasoning, spatial reasoning, and math tasks.
Table Performance models on various topics within the Math- QA dataset. laput dependency consistently improves performance. with Mamba consistently outperforming S4-113
The results presented in Tables T 2 highhlihh several critical observations regarding the perfor- mance of various models across different composition tasks. Notably, Mamba (Gu & Dao 2023) consistently outperforms the S4-H3 (Gu et al., 2022 Fu et al.) 2023) model, despite both having almost the same number of parameters. This performance gap underscores the importance of input- dependence in model design, as Mamba's ' architecture better leverages input information to achieve superior results. Additionally, while GPT-4o is the most performant overall, struggles with many tasks, including those that seem simple to humans, such as logical expression chaining, as evidenced by its performance on the BIG-Bench Hard (Suzgun et al. (022) benchmark. This indicates that even state-of-the the-ttrrt models like GPT-4o have limitations in solving complex composition tasks, which numerically justifies our theoretical findings. Accuracy for all models is calculated as the number of correct answers divided by the total number of samples.
Compositional tasks Having demonstrated that models encounter difficulties even with more straightforward composition tasks, we now examine their performance on more complex com- positional tasks. Given their proven inability to perform function composition, as established in Theorem
[ it is entirely anticipated that their performance on these tasks will be suboptimal. We explore three compositional tasks: (i) multi-digit multiplication, (ii) dynamic programming, and (iii)
Einstein's 's puzzle.
For the multi-digit multiplication task, we generate question-answer pairs such as "What is times 90?" with the answer being "450". This task involves multiplying two numbers, and y = (y/, ./...... )k). where each number can have up to & digits. Consequently, there are 9 x (0(h-1) possible combinations for each number. In our experiments, we set & to and found that both Attention and -SM-based models are unable to solve the 5-by-5 digit multiplication task, in the case of GPT-4o with CoT prompting (A-
(I1, 22. 2x)
Jambe (btbertton
Multip lication Performance
Jambe JAttention
Mambel Zero Shet Puode Performance
Zaro- Zero-Shot DP Performance
4.33
6:1
Ieneemaane Grore
6.44
6:2
Momba
Ar4
5:30
302
441
Rage Maltplad
Frobium
Figure 2: Jamba Lieber et al. 20044 performance on multiplication, DP and puzzle tasks. For DP various models shown. All struggle with compositional tasks, especially for larger input size.
19

---

Published as a conference paper at ICLR 2025
Dynamic programming (DP) recursively decomposes complex problems into simpler sub problems, making solutions compositional by nature. We consider a classic relaxation of the NP-complete Maximum Weighted Independent Set problem (Kleinberg & Tardos 2005): Given sequence of integers, find a subsequence with the highest sum such that no two numbers in the subsequence are adjacent in the original sequence. DP we restrict each integer to the range [-5,5] 5] and follow the generation steps as in (Dziri et al. 2023
solve This relaxation in (n)) time. For our experiments,
with an input list containing from 2 to 6 elements. Prompting details are shown in the A C.3.3
Einstein's 's puzzle is a well-known logic puzzle commonly used as a benchmark for solving constraint satisfaction problems (Prosser [993). involves a series of houses with various attributes, and the objective is to determine which attributes correspond to each home by interpreting a set of predefined natural language clues or constraints. The solution to the puzzle represented as a matrix of size H x A, where H denotes the number of houses and A represents the number of attributes. As H and A increase, synthesizing partial solutions that satisfy individual constraints becomes increasingly compositionally complex. Qualitative examples and details about data generation for this task are provided in the A
B.2 COT EXPERIMENTS
Next, we evaluate how the popular chain-of-thought (Co'T) prompting method (Wei et al. 2022 affects the performance of GPT-40 (OpenAl 2023). Jamba LLeberr et al.) 2024). Mamba (Gu & Dao 2023) and S4-H3 (Gu al. 2022) models on compositional tasks from Sec. B.1. CoT improves
performance but does not solve the problem. Details of the experiments and examples of full prompts can be found in the A AD
B.3 ERROR ANALYSIS
We focus on graph analysis of errors, emphasizing multi-digit multiplication because this problem is easier to interpret and understand. From this analysis, we obtain a few interesting conclusions about how errors happen and then propagate inside SSM-based LLMs (Fu et al. 2023 Gu & Dao 2023 Mirzaee & Kordjamshidi 2022).
Computation Graph To study the propagation of errors and its dependency input size, we define A as a deterministic algorithm (function) and FA as the set of primitives (functions) the algorithm employs during execution. Given inputs x to the algorithm A, we define the static computation graph of A A(x), denoted as G((x)) as G(()) = (V, E, s, op). a directed acyclic graph.
Nodes V represent all variable values during A's execution, where each node V has associated value s(v) E R. Edges E represent function arguments involved in computations: for each non- source node V, let U {u1,-- / u₁} V be its parent nodes. Then, s(v) I (u,, Ut)) for some FA. Since each node v is uniquely determined by the computation of a single primitive f as the operator function that yields s(v). Let S C V be the source nodes of G A(x)) and without loss of generality, let o E V be its sole leaf node. By definition, S = x and A(x) = s()), representing the input and output of A, respectively. To evaluate language model's ability follow algorithm A, we must linearize GA(x) (arrange the nodes in a linear sequence that respects the dependencies). This means if a node u is a parent of node the u should appear before in the sequence. Since we only consider autoregressive models, this linearization must also be a topological ordering. A topological order ensures that every node appears after its parent nodes, maintaining the correct order of computations. This is crucial for correctly following the sequence of operations defined by the algorithm A.
f. we define op: V + FF, op(r)
To instantiate G let FA = {one-digit multiplication, sum, mod 10, carry over, concatenation). Source nodes S are digits of input numbers, leaf node o is the final output, and intermediate nodes w are partial results generated during the execution of the long-form multiplication algorithm (see
Fig. 3
The corresponding algorithm is on the left of the Fig. Alg.
Error propagation We examine errors in SSMs, focusing on how they propagate through compu- tation steps. Fig. 4 shows an example from the S4-H3 model performing multi-digit multiplication using CoT prompting. In this case, the model multiplies 9 by 63. correctly computes 9 3 = 27 but mistakenly carries over '3' instead of '2', leading an incorrect middle digit in the final answer
20

---

Published as a conference paper at ICLR 2025
Algorithm Multiply two numbers
1: function (ULTIPLY(c v(1..)))
multiply each 1y4]
for tto
carry= 0
72
4:
for p do
8
783
5:
[=x0]] x v(1
6:
f+= carry
add carry
7:
carry = + 10
63
digits bj mod
end for
10:
summands[i] digits
11:
end for
Figure 3: Example of 2-by-1 digit multiplication
12:
product Σx1 summands(g + i-j
(87 x 9). Operations on graph include: inputs, multiply 1-digit, carry, sum, mod 10 and output.
10
13:
return product
14:
end function
despite correct addition in later steps. This highlights propagation errors, where an initial mistake affects later steps. Our analysis shows these errors are 2-4 times more common than local errors, consistent with findings from Dziri et al. (2023). This suggests SSMs handle single-step tasks well but struggle with multi-step reasoning, leading compounded errors.
9
68
54
6
20
27
4
3
Figure 4: Error Propagation. Carry operation outputs number instead of 2 from node '27', and that is further propagated, yielding incorrect solution in the middle digit, although all other steps were done right.
Figure 5: SSMs and Transformers learn shortcuts that seem solve function composition but fail with larger inputs and out-of-distribution data.
SSMs learn shortcuts The performance of SSMs provides valuable insights into their behavior. These models often predict partially correct answers when the overall response is incorrect. For example, using Mamba (Gu & Dao 2023) for 2-by-2 digit multiplication, the first and last digits are usually accurate. The first two and last digits in larger multiplications tend to be correct. Using Relative Information Gain (RIG) analysis (Dziri et al., 2023), we find that SSMs learn shortcuts, performing fewer operations (illustrated by the red and green subgraphs in Fig. 55. This allows them to frequently predict peripheral digits correctly. For instance, the model multiplies 8 and 5 to compute the last digit, carrying last digit. RIG analysis reveals strong correlation between the first digit (or first two digits) of the output and the first digit (or first two digits) of the input numbers.
the end, mimicking human multiplication, and accurately predicting the
These models leverage task distribution shortcuts to guess partial answers without whole multi-step reasoning. Increasing the number of Chain-of-Thought (CoT) steps doesn't constantly improve results, especially for larger input sizes (deeper computation graphs). If the model encounters relevant subgraphs during training, inference seems highly compositional but is based on shortcuts (Geirhos) et al., 2020: Liu al. 2023a Tang et al. 2023 Du et al. 2022). These experiments indicate that when an output element heavily relies on few input features, SSMs recognize this correlation during training and map these features to predict the output during testing. This gives the false impression of performing compositional reasoning while bypassing rigorous multi-hop reasoning (Yang et al.
2024).
21

---

Published as a conference paper at ICLR 2025
To multiply two numbers, start by multiplying the rightmost digit of the multiplicand by each digit of the multiplier, writing down the products and carrying over any remainders. Ropeat this process for each digit of the multiplicand, and then add up all the partial products to obtain the final result. Here are examples:
question: what's a 32 times 82 Answer 256.
Question: what's 69 times 37 Answer 207.
Question: what's 93 t times 67 Answer 558.
Question: what's a 76 times Answer:
Figure 6: Example prompt for the multiplication task used for the few-shot prompting.
B.4 LEARNING ALGORITHMIC COMPOSITIONS
Finally, we conduct comprehensive analysis of the capabilities of SSM-based models, along with GPT-4o (OpenAl 2023), to "learn" discrete algorithms. This analysis is performed using two tasks that require the composition multiple discrete sub-tasks. By empirically examining the models' algorithmic learning through compositionality testing, we observe their inability to effectively perform these tasks, even when provided with few-shot prompts and CoT examples (Wei al., 2022). This suggests that within the framework of in-context learning, SSM and Transformer-basee models fail to attain compositional learning when constrained to fixed number of samples. Details in the A
C COMPOSITIONAL TASKS DETAILS
C.I MULTIPLICATION
We show examples of few-shot and CoT prompting methods for multiplication task (Figs. 6
C.2 EINSTEIN'S S PUZZLE
Following Dziri et al. (003), we first define a set of properties such as "Color", "PhoneModel", and "Pet", along with their corresponding values in natural language templates (e.g.. "The house has red color."). We then create a basic and clear set of clue types:
Data Construction
found at: For example, "Alice lives House 2."
2. same_ same_house For example, "The person who is a cat lover lives in the house that has red color."
pereet_leftt For example, "The person who has a dog as pet lives to the left the person who lives in red house."
4. besides: For example, "The person who has a dog as a pet and the person who has a red house live next to each other."
Additionally, we introduce more challenging clue types for auxiliary experiments, such as not_a tt, left_ of (not necessarily directly left), and two_ between. These harder clues used to test the robustness and versatility of our models.
Graph Construction To address the complex compositional reasoning required for a logical grid puzzle, we utilize existing puzzle solvers de Moura & Bjømer (2088) to generate the computation graph. Our algorithm follows basic greedy principle: it applies the minimum number of rules necessary to solve any cell. Specifically, if single rule can solve a cell, that rule is applied.
The algorithm iterates through all clues in the clue set, seeking combinations that can solve any cell in the table. Although this approach may not be the most efficient, it enables models to have explicit scratchpad verbalization via an intuitive computation graph. Fig x shows an example of a scratchpad.
22

---

Published as a conference paper at ICLR 2025
Question: What is 904 times 743
Scratchpad: Let a perform the multiplication step by step:
Let's multiply 904 by the digit in the ones place of 74, which is 4.
1. Multiply by the digit in the ones place 904, which is 4. This gives 4 x 4 16. Write down the result 6 and carry over the to the next step.
2. Multiply 4 the digit in the tens place of 904, which is 0, Add the carryover from the previous step account for this. This gives
x 4) + 1. write down the result
3. Multip'y by the digit in the hundreds place of 904, which is 9.
This gives x 4 36. Write down the result 36.
4. The partial product for this step is A=3616 which is the concateration the digits we found each step.
Now, let's multiply 904 by the digit in the tens place of 74, which is 7.
5. Multiply by the digit in the ones place 904, which is 4. This gives 4 x 7 28. Write down the result 8 and carry over the to the next step.
6. Multiply 7 the digit in the tens place of 904, which is 0. Add the carryover from the previous step account for this. This gives x 7) + 2 2. Write down the result 2.
7. Multip'y 7 by the digit in the hundreds place of 904, which is 9. rhis gives
63. write down the result 63.
8. The partial product for this step H-6328 which is the concateration the digits we found each step.
Now, let's sum the 2 partial products and B, and take into account the position of each digit: A=3616 (from multiplication by 4) and B-6328 (from multiplication by but shifted one place to the left, it bocomes 63280) The final answer is 3616 x 1 + 6328 x 10 3616 + 63280 = 66896.
Figure A sample scratchpad for the multiplication task.
23

---

Published as a conference paper at ICLR 2025
This is Logic puzzle. There houses (numbered the left, on the right). Each has a different person in them. They have different characteristics:
Each person has unique name: peter, eric, arnold
People have different favorite sporta: soccer, tennis, basketball People different car models: tesla model ford f150, toyota camry
1. The person wno owns Ford F-150 is the person who loves tennis.
2. Arnold is in the third house.
3. The person who owns Toyota Camry directly left of the person
who owns a Ford F-150.
4. Eric is the person who owns Toyota Camry.
5. The person who loves basketball is Eric.
loves tennis and the person who loves soccer to each other.
6. The person
Let think step by step. Please first briefly talk about your
reasoning and show your final solution by filling the blanks in the below table.
$ House:
$ Name:
$ Sports:
$ Car:
$ House:
$ Name:
$ Sports: $ Car:
House:
$ Name: $ Sports:
Car:
Reasoning:
Step 1: First apply clue <Arnold is in the third house.> We know that The Name in house is arnold.
Step Then combine clues: <The person who loves tennis and the person who loves soccer are next te each other.> <The person who loves basketball is Bric.> Unique Values Rules and the fixed table structure. We know that The Name in house 1 is eric. The FavoriteSport in house is basketball. The Name in house 2 is peter.
Step 3: Then apply clue <Eric the person who owns Toyota Camry.> we know that The CarModel in house 1 toyota camry.
Step 4: Then apply clue <Thh person who owns Toyota Camry is directly left of the person who owns Ford F-150.> and Unique Values we know house
that The CarModel tesla model. 3.
ford f150. The CarModel house
Step 5: Then apply clue <The person who owns Ford F-150 is the person who loves tennis.> and Unique Values We know that The FavoriteSport in house 2 is tennis. The FavoriteSport in house is soccer. The puzzle solved.
Final solution:
House:
Name: Bric Sports: Basketball $ Car: Camry
House: 2 Name: Peter
Sports: Tennis
$ Car: Ford
House: 3 Name: Arnold
Sports: Soccer
$ Car: Tesla
Figure 8: A sample scratchpad for the Einstein's puzzle task.
C.3 DYNAMIC PROGRAMMING
We show examples of zero/few-shot and CoT prompting methods for dynamic programming task (Figs. 9 10P. following Dziri et al. 20233
24

---

Published as a conference paper at ICLR 2025
Given sequence of integers, find subsequence with the highest sum, such that no two numbers in the subsequence are adjacent the original sequence.
Cutput iist with "I" for chosen numbers and "2" for unchosen ones. If multiple solutions exist, select the lexi cographicaalll smal lest. input 13, 2, ', 5, 21.
Figure 9: Example prompt for the DP task, used for zero-shot and few-shot settings.
Question: Let 's solve input 13, 2, 1, 5, 21.
Scratchpad: [p[ max (input [4], 0) max (2, 0)
dp [3] max (input [3], input [4], 0) max (5, 2, 0)
dp [2] max (dp[3), input [2] + dp[4], 0) = max (5, + 2, 0)
dp [1] = max (dp [2), input [1] + dp[3), 0) = max (5, + 5, 0) = 7
dp max (dp[l), input [0] dp 0) max (7, + 5, 0)
Finally, we reconstruct the lexi cexicooappicca11 smallest subsequence that fulfills the task objective by selecting numbers as follows. We store the result
list named "output".
Let can use next item True.
Since dp[0] -- input[0] + dp[2] (8 = + 5) and can_use_next_itee
Truc, we store output [0] = 1. We update can_use_next_iton = False.
Since dpli] != input + dp[3] (7 I= + 5) can_usc_ncxt_ _itemmemm__
False, store output[l] = =. We update can_use_next_iie
True.
Since dp[2] != input[2] + dp[4] (5 !-
2) or san_use_next_ite item
False, we store output [2] - 2. We update can_use_next_ites item - True.
Since 13] == 13] (5 == 5) and can_use_next_iten == True,
store output
1. We update can can_use_next_iie item False.
use next item False, we Since dpl4. input |4] (2 2) or use
store output 2.
Reconstructing all together, output-[1, 2, 2, 1, 21.
Figure 10: A sample scratchpad for the DP task.
D DETAILS OF COT EXPERIMENTS
D.1 MAIN COT EXPERIMENTS
We plot the performance of Jamba Lieber et al. (2024) multiplication and puzzle tasks and various models on DP tasks after using COT.
The leftmost heatmap Fig. I represents the Jamba Lieber et (2024) model's multiplication performance, showing a consistently high performance for multipliers of and 2, but noticeable decline as the multipliers increase, particularly beyond The middle heatmap compares the performance of four models GPT-4o OpenA] (2023). Jamba Lieber et al. (2024), Mamba Gu Dao 2023), and S4-H3 Gu et al. (2022); Fu et al. (2023) -n dynamic programming tasks with CoT prompting Wei et al. (2022). GPT-40 OpenAl (0233 consistently outperforms the other models, maintaining high performance even for larger problem list sizes, while the performance of the other models decreases more rapidly. The rightmost heatmap displays Jamba's 's puzzle-solving performance, indicating high accuracy for simpler puzzles with fewer attributes but a steep decline as the complexity increases. These visualizations highlight that while CoT prompting Wei et al. (0022)
25

---

Published as a conference paper at ICLR 2025
Jamba (Attention Mambu) CUT HuRiplication Performanc
Janika (Attestion Nambal Cal Puzzle Performance
0.4
6.20
0.11
Dipt Nuttyker
1.09
6:90
6.41
0.1
6:00
Digi Haloppacyy
Figure 11: Jamba's Lieber et al. (2024) performance on multiplication and puzzle tasks improves with CoT, though not fully solved. Other models were tested on the DP task, where they failed at higher input sizes, despite CoT.
generally enhances model performance; its effectiveness varies significantly across different models and task complexities.
D.2 PERFORMANCE OF OTHER MODELS ON MULTIPLICATION AND PUZZLE TASKS
We observe the same pattern on both tasks, for all the models Figs. is always the best model, followed by Jamba Lieber et al. (2024), then Mamba Gu & Dao (203))
B
GPT-4o OpenAl (2023)
then $3-H3 Fu et al. 2003): ) Gu et al. (2022). While CoT helps, it is not enough to solve the task.
Multiplication
Multiplication
Multiplication
Parformance Digit Hubpilier
Performanca Scor
1.00
5.87
1.10
0.50
0.77
1.40
Dight
1.00
6.38
627
0.57
+-
1:00
0.88
0.29
5.04
1.40
0,68
6.04
1.00
0.55
0.59
6:33
0.50
1.00
2.30
0.04
5.0L
0.30
1.50
0.21
0.03
5.00
Digit Nuttpptedd By
Dige Hutiplled
Digit Muttiplled By
Figure 12: Comparison of different models multiplication task using COT.
GPT-4o CoT Puzzle Performance
Mamba CoT Puzzee Performance
54-#3 CoT Puzzle Performance
1:00
1:49
0.89
9.77
0.6h
6:42
0.59
0.77
0.44
6.59
8.79
9.49
Parformance Scors
Number of boueet
0.54
0:36
8:00
0:33
44
0:42
of
Parformmnn
Number afattriluutes
Number attriibatee
Number attrributen
Figure 13: Comparison of different models on puzzle task using COT.
D.3 FEW-SHOT PROMPTING MULTIPLICATION RESULTS
We investigate whether few-show prompting (giving model few input/output pairs) and then asking for the answer to the new problem help. Fig. [4]ssows the results, and consistently CoT outperforms Few-shot prompting, and Few-shot prompting outperforms Zero-shot prompting.
26

---

Published as a conference paper at ICLR 2025
GPT-46 Fow Multiplication Performance
Multiplictiion
54-H3 Sow-Sott Multiplication Performance
2.80
2.00
Digit Hukphier
Parformance Score
Parformance
Digtt
0.20
6.21
0.82
0.50
0.00
Multippied
Digit Nultiplled
Figure 14: Comparison of different models on multiplication task using few-shot prompting.
E ALGORITHMIC COMPOSITIONS
Following Thomm et al. (2024), we evaluate the models using the PE's Neighbour (PEN) task.
This task involves navigating from one word to the next based on specified matching criterion and outputting all the neighbors encountered along the way. The PEN task, inspired by [Abnar et al. (2023)
and rooted in the Pointer Value Retrieval framework Zhang et al. (002).. is particularly compelling due to its four sub-tasks, which test the necessary sub-operations for PEN. These sub-tasks are: (i) Copy words, (ii) Reverse Copy (copying words in reverse order, where words consist of multiple tokens), (iii) PE (outputting words in the matching chain instead of neighbors), and (iv) PE Verbose (PEV) outputting both the words the matching sequence and their neighbors. These sub-tasks essential because, to predict the next word, the model must: take the current word in the answer, obtain the left neighbor (learned in Reverse Copy), match it (learned in PE), and then obtain the right neighbor (learned in Copy). PEV is considered sub-task because it requires solving the same problem as PEN but with the added complexity of providing both matching words and their neighbors. PEN, on the other hand, only requires outputting the neighbors. For accurate text-token prediction the model cannot simply replicate the last matching sequence word from the previous answers, it must first infer from the neighbour. To increase the task's complexity. "attention traps" or "doppelgangers" are introduced. These traps create additional matching possibilities by allowing each neighbor to match two other words, thus tempting the model to match from the neighbor of a matching sequence instead. This added layer of difficulty further challenges the models' ability to learn and compose discrete algorithms effectively. Pointer Execution Reverse Multicount (PER Multi) shares conceptual similarities with the PEN task; however, instead of matching forward and predicting the current word or its neighbor, the task involves first outputting the last word in the matching sequence and then proceeding backward. Consequently, to accurately predict the first word, the model must identify the end of the matching sequence and output that word. The model needs to count the total number of matchings and the number of matchings that align to the left in the given word order. The answer requires multiplying these two counts, introducing non-linearity. For this task, we omit any attention traps, as there are no neighbors involved. In the A E we show concrete prompt examples and share the code.
We conducted extensive evaluations on 500 test samples using various models under different condi- tions: zero-shot, few-shot (providing a limited number of input-output pairs), and CoT prompting Weil ctt al. 2022). Remarkably, none of the models, including the state-of-the-art GPT-4o OpenAl (002)), succeeded in solving the PEN task Thomm et al. (2024). Typically, models correctly generated the initial strings but then halted prematurely or produced random strings. The same pattern of failure observed with the PER Multi-task. Specifically, GPT-4o achieved only 1% and 9% accuracy using few-shot and CoT prompting, respectively, failing to solve the task. The marginal success of GPTT-4o is attributed to its substantially larger parameter count compared to SSM-based models [B.
27

---

Published as a conference paper at ICLR 2025
Table Model Accuracy for PEN task
Table 4: Model Accuracy for PER Multi task
Model
Prompt Setting
Accuracy [%]
Model
Prompt Setting
Accuracy [%]
Zero-shol
0.30
Zero-shal
0.00
GPT-4o
Few-shot
0.90
GPT-4o
Few-shot
0.01
CoT
0.00
CoT
0.09
Zoro-shot
0.00
Zero-shot
0.00
Jamha
Few-shat
0.00
Jamha
Few-shot
0.00
Col
0.00
CoT
0.00
Zero-shot
Zero-sbot
Mamba
Fow-shot
0.00
Mamba
Fow-shot
0.00
CoT
0.00
CoT
0.00
Zero-shot
0.00
7em-shot
0.00
Few-shot
Col
0.00
CoT
0.00
In the following subsections, we focus on showing the prompts in few-shot and CoT settings for PEN and PER Multitasks. Moreover, we show the code we used to generate the samples.
E. PROMPTS FOR SSM AND ATTENTION-BASED MODELS FOR PEN TASK
Example: eg jy vm3ze si22f mn411 2f5ka ki7xd ew0si xp3og i15js xn
my7ec xu2gb if2my fy3so ec2il obSch kt5is zc4xp
ka3mj oglud zš2ka yh3ux
hx2kt ve2pf jy4qd 1jlxu wyShx bd4xa my4ec atlkb jy3qd uxlfl ew3si ds2qz
qd7ew xalay silzf ch41j is3rf fl6xn mj7wy zy6rq zh2gu bj3rb 150my pg5ds
yvšhs zu3ob ta7qi j12bj mjlwy rq7ul mn3fw ay4qu kt2if kr3cb pr0ah tg0at
uelvx xdlpd wy4hx dr mk0vj smüpg j12mo rbibd i12js vn6kr km4aq eg7nn
ka6mj qu4ve hx7kt 1121b ec6il ud2vn di3xs pa6ji qd6ew yx7zu rh4qn 1blki
js5rf iv3yh jjofa kb3am 1h6yk soliv bx6ra qalvm mw7bm gb2xo uyōms qb2zy
zm0pz xo4tg zx5jm
Answer: jy kabmj zřbka ec6il jsbrf ew0si wy4hx qd6ew mjlwy 1=0my i12js my4ec silzf kt2if hx7kt 1y4qd
<FEW MORE EXAMPLES>
Your question: ey kj5yo jzCaa nu4yw gp2ro mv6kj nk2çz tr3mp ro7kk
tu5xj rk0sj ad21x up3vd ta7rv q26ob re7nt aa4nk mb6mm ob7us jw5wb 4t4jz
nn4sr wtOjz evOfa gplro srlmu sjūku xs0ta usSup mр6jи válgp xj3cs sj7ku
ol3vv vd3gp wd2mv wr4ez dg0py ro5rk jt bvocf yb2qv ch2ss xa3be nb5id
1x4it dz5ht wb5wd fb3ax factu jn5ps rv7qj qa7el rn7ad 1z3fk mmltr yd3lv
ntoxs 1h42k mr3ou ja5an giSub rk4aj wm7zm jz3aa be4mb kw3bh qj4xa eg0mi
112rn kving 5mz ye3kg yr5ol nk7qz ubldg objus es7se gw4vk ey4wm q22ob
qv4ii xz4hc 110yb oy4qu zmžyr uplvd ou7li rx4we ywlgi aa2nk yo3qt yz5ox
vv6nn
us7up
clearly mark your answer by writing 'Anawer: <your answer> last line.
Figure 15: Prompt for the PEN task, showcasing few-shot learning examples. Each word's start and end are encoded as distinct tokens, so a model can pattern- matte the respective token to do the matching operation.
28

---

Published as a conference paper at ICLR 2025
Prompt the PEN few-shot CoT examples and description.
give you sequence of words. Each word has four characters plus middle, words separated spaces. Start with the leftmost word. Output neighborr Then, match the last two characters of the current word (.e., not neighbor) the word starting with those two characters. Again, output the neighbor. Do this until your current word (not the neighbor) has no match anymore.
Example: xh je qwose zslgh xvévn maf vnlnh akIks safiv ghi daSgy kslew 78k emšes squ ftmme gübee emkes znāge kasew by me7af jellrr chdri pwchi rk7ch den ew 3ek yyy log qu7fp gléva vnšzm okil eeftw skfch hefegi jefem qp2es ewfrk qutigr fi'me fpllqw sabok sd7pa je3em widda eq7sa ivOdl 2s7gh vizke vaseq fetwi xl hgOld cglsa ja2ub whávv oeks gellix ytbes velga ubt lam rf2el kušhg xg5bk me?yg aqSuw sh7pw suTok wtSot jodhd palje lobva hosec wpblc es7fe yw2ka gy3ad nrlly amdy: pilrl ik0tn ubSig shOja ee2it nhtqze
xzlma selts, ismm kelxv cb6it rx2mz wjjaf.
leftmost
right neighhor jr,
first output
is jr.
Now, we need to find a word that starts with xh. The word is xh7pw. Its right neighhour is sa7ok, so the next output word is sa7ok. ourput word rk7cb. right neighbour cqdsa, so next outpett word cquka Now. we nced to find a word that starts with dv. The word is dv2an. Its right neighbour is ew3rk, so the next output word is ew 3rk.
Now, need find word that starts with pw. The word pwóhi. Its right neighbour rk7ch, so the
Now, we need
a word
starts with bg word hgghdv.
Now, need find word that starts with The word is snóāv. Its right neighbour qhiva, the
output ward ghiva.
Now, we need to find a word that starts with iv. The word iv0dl.
right neightour 257 so the next output word zshh..
New. we need to find a word that starts with v1. The word vi2kc. Its right neighbour is vašey, so the next output word is vašcu.
Now, need find word that starts with The word is ke Its right neighhour chéft,, the
ourput word chóft.
Now, we need to find a word that starts with xv. The word is xvvvn. Its right neighbour is me3af, so the next ouipet word me3uf.
Now, we need to find a word that starts with The word is vnšzn. Its right neighbour oklks, so the next outpur word okl word
Now, we need
starts
The werd is zn5qv. Its right neighbour ksSew, so the
output word kssew.
Now, we ueed to find a word that starts with qv. The word is gvegt Its right neighibour is ft7me, so the next output word is ft7me.
Now, need find a ward that starts with The word gi3be. Its right neighbour em3as, the output word is em33e. hc7qi. right neighhour is je7em,
Now, we need
a word
starts
next ourput word is jæ7em.
There is no word that starts with gl. so we are done with the matching.
Therefore the answer is: sa7ok rk7ch cuésa ew33k ghiva 257gh vuãcq chôfit melaf ok ksSew fi7me em3rs je7em.
<FEW MORE EXAMPLES>
Your question: up cb ch5ya gbólt uuble vnūpe ogdel md6ki jxOph molki m4x0x vplex eplaj isSam 5g5lb te3rz eqlbe eb0mnd he2ep 1e2re eftyp vnSpe uilyi khi ji qg 2mg am4yp ez ltšf bwdeg le wn5kd kbāji letwk vpdex ytáig rxfgh ey4dk jiMe laj ldg laDke wk7sl amovp ziOup kiSkb ek7uu reting ossez vpšiz dxfse xp2km fe3re beThw rx2gb yp6ag gb4it ardes fi7vn Inl fiSva pházi m4is kd2bz, fi alökk ki2kch yobey teliy fd5at qbTia hn2xp chémd yalwn gd7sg sjag rphi up isdum seSui re5vq eg4ag afffj fhrjx l14ic sl4ch qe sp5id gishff de do rzlis knı6yo vgálz up5sp wediv Reason step by step. Clearly mark your answer by writing 'Answer: syour answer> as last line.
29

---

Published as a conference paper at ICLR 2025
E.2 PEN GENERATION CODE
iegort ("aeec"abed www.eechhhhhiiiee.....e..e 1oie www.
Letter_chats 11st
biq sig_intter_cmaaee Liat ("ABCDEFOE www.ECEEEOOLLLLLOOOOOOO. ger
olass BataContig)
def lett foelf, nin.lem 1en, nax Jen, nin_hops, rax,hops, lears node, arbiguous, no green, confusion)
isx_inn nax_ian
selt his-aap min_hspa
ni__nsaaaaaaa nax_hapa
lelrr vode
r Lnbnniguu anbigueus
ne 7.30 green cor Fuston no green confuston
ded
zeturn qatat::
default)
class
data
Ten
sel r. renghh
higs higs
data cfg max Ter +1
self.2ops_isx data hos
self (il.-all_ Stppls 1e0 jen, Jein (t) for in cuaztceia.prodeee chars, cepeate21)
selt earn rode data wwg.gerg.ee ("eeam mode", "hest*)
anoigunu self aese generst deublc www.utttttttottnnoooo (ac.f, (LSerples)
("arbl ("wrbl guous", Patze)
dig wesssseg.eeeee.ee qes on__ssee__onnuiie Polse)
ng.esangettollf Lon son..hongshhiggh
zarples
anavers
length ip.aandar cho.catienttia
sunetching_ ap rendos chicoo azance toolf, low, sio gintself hora Highar, lengch // 201) Juplen, lesgth aeplace Folse!
chols_chooos randos the patching reguence we22
the nostsione
positions rg.randen.ctme choice ara.gea (1,, length), siseennatcchinggugg replacenraise)
(lengchi)
cxsstion.xordla -** for range (langchi)
sensining pos itsins 62 randon ponnutatioon Ila for la cangetl, tength) ie not in positions]) gasstion_xsreet imueationxxoree
learsag
for pas in positiona:
wortiol [pos] (tuple Shoics foct) apurendo toeif dara.choiooo tuple_choloossend questioonoodddee (pos))
ont
positions_ mp.random.... persuaationppaaiii question vcrdb210] cuple choices [ont]
answer (question vcrd62101]
the doppeigangers of neighbours will
cositiins__ooniee contuse rp. setsitffelto tro azange i., longthl, ponaticna__ext) 18 (posssiioons_mett sp randen, asstiin ipoit
two big Jetters cp.randon.ooooitoo oloion ( data choloes, sizend, replacense f. (aanbiguuas)
question words2 [pos] ccuple choiced fort] twe big lettersfo" tuple ahotcesfone 11)
question (pot fusellll
ituple choloes two big lesterefll tuple choloestone
append (queattion
ent
cnt_confuse confose)
rensining next posictions rgg.randnn.gen iindongeeruuattioni for in ranget), Tengthl st 1 not in postctons next and not in positions confosel)
qusatioq_vorial vordao [poa]
(uple__hoiooe((tt)) ap.randos, choics tsold, dara_choieaa tubla_choiewsjent
green ent to
cnt in
pe9 censining_oot__pssttee (oo.loosoordallpou) (buple_choicc(ess
toolf, dare
cot. +=
ansuer ansuer learseazt Iigestioo words21011
gas positionz:
messer_lestnneee:
(queer xorded (pos])
saswee_aceoo =
in rasea (anaver leaznagg)
anoner_Jeuneet
sneser sequext dpperdiinnee learmnest (5]]
ansuer, euouer.zeverze zeversa()
for in rasge range (langshl:
qusacioa appondi quest ton (13) quastiinn ramples, qqueriiiue tec_ sto)
(t"pe
".iin joinoet for guastion_vonde]:
swis. Learr_node
"seg":
j.jonionneves_ Jearnsogf
ollf solf. leain rode *oognext
anowerd "ppend(" "_joiniangve__ppppedd
Aspand p.joinnonaeee__lermmees zeturo sueples, anииaса generctatooll a_sampleal zeturn samples, answers
Figure 16: Code utilized for generating instances of the PEN task and its associated subtasks. The
hyperparameters employed include a length ranging between [40, 50] and a number of hops ranging between [10, 20).
30

---

Published as a conference paper at ICLR 2025
E.3 PER MULTI-GENERATION CODE
import Abaztools
ingort nurgy as ng
chare
bataConfig:
def 1015 conit, minuien, nas_ien, Logname, learn_node""aee")
min min
delf Cognare lognase
celf Learn. rode learn mode
key,
Pointersreeutionne www.eattiineeeeeaiiiiioooo decauit)
seturn getatis lsels,
class
mints tssif, dats cigl
delr- Tengghhh higher dara nax Ten +.]
nell loghaaeee data cfg tograme
itarteols, product ceppate21)
self
data_cfe. est ("Iearmnnode", tseaf)
assest self. in ""ee" "mustise"' Seqqrv", 'miltiserer")
carplesiae]e
lengths ug.arangettell length sele, higher)
carples
anavees
Tength op. candar. cho.co
riple cholces des up randon choice Lumllss, Tength 1-3, reglace-Falae!
eoeette tuple
"uple
cholcss:
randen permutation ton ion ctaple.choteestte
soutiled septe dchiiiea is sandon par.pppaaaaaiii (aple_eaiinn [2-]]]
vordo [chi
sis (shuffled topleeteopppppeeeeeee tuple_cwineel sadflee
words vords.sgpedd sppeddilsst word)
in self.
segnext (vords,
telt.leam
else:
shange the 2taple che staze of the peaze word to aundas ons wordb.indox indoindoxxtta supla_choiceat-1 xorde(1dx] [2:]
start vardelies)
anaver, answes____ett www..anive_.reee anivn_eeegaat (xerds, start, seit.ciern_rrce) self rear
anaver zeversedi (x] for
enurerace (CnSHGe)
if belfniearnnnoee rode
Lsequees
question ftaandd [seit. ( ieaen_node]; F. (vords) samples diuerrtgusassies aaswero, apperrd
aniver:
(anowex))
def selve_ segnewt: Iself, worda, start, node]
anaver_next
querent_vozt www.reeteeeeeoeocccoooee word)
16x inddo.
shile Teue:
nat-hhingaeee espand (crrenntttrett__xcor
answer left app.aapeeddd left)
next word (i 1) for 3, ennnerate (words) iE vistertowich fourzent 2011
break
assect len [sexttraeed
cursent_vvrd, nar_iti [oxt_xord]j]
1dki
left --
break
if "rov" in rodes
raccNing seg,
"ealti" in
ansuer [1
i, al enuzerata thtthhsneee dioner_a_leftt))
(i)-
retuzn onaver
return astchiing ing.eng
zarples, cxmplesii zeturn susples, enswaro
Figure 17: Code employed for generating instances of the Pointer Execution Reverse Multicount task and associated subtasks. The hyperparameters employed include a length ranging between [10, 20).
31


Reviews:
[{"review_id": "hFXwPsE9qt", "reviewer": "Reviewer_yPps", "summary": "The paper theoretically and empirically studies the limitations of the computational power of SSMs in terms of effective space complexity and their ability to do function composition.", "questions": "The following questions are about Theorem 1.\n1. The proof seems to rely on the specific ordering of $g$ followed by $f$ followed by $x$ in the prompt. Does a similar proof work when these pieces are in different orders? In particular, what about the order that would intuitively be the easiest for the SSM: $x$ followed by $g$ followed by $f$? (The intuition here comes from the fact that a streaming algorithm taking in $(x, g, f)$ in this order wouldn't need to store the entire table of $f$ or $g$.)\n\nThe following questions are about Theorem 2.\n1. How's the definition of CoT different from just autoregressive decoding?\n\nThe following questions are about Theorem 4.\n1. Lines 74 & 386: Isn't $\\mathsf{L}$ a class of decision problems? Shouldn't one say $\\mathsf{FL}$ instead of $\\mathsf{L}$ here?\n2. How is it possible for $p, d$ to grow with $N$? While an SSM can take an input of variable length $N$, its $p$ and $d$ must be fixed, right? I don't know what it means for the precision and hidden dimension of an SSM to increase as the input sequence becomes longer. SSMs are unlike boolean circuits which require a differently-sized circuit for every possible input size.\n3. While the theorem statement assumes $p, d = O(\\mathrm{poly}(N))$, the proof assumes $d = O(1), p = O(\\log N)$. For example, line 359 says \"each element of these matrices can be represented using $O(\\log N)$ bits.\" Line 377 says \"numbers are represented with $O(\\log N)$ bits of precision.\" Line 379 says \"we only need to keep the current and previous hidden states\", which require $O(dp)$ space, hence implicitly assuming $dp = O(\\log N)$.\n4. How are $A_t, B_t, C_t, D_t$ (which are functions of $x_t$) computed? Some assumption on the space complexity of these computations is missing from the theorem statement.\n5. This is a small detail, but in the current formulation where the input sequence is a bunch of vectors of real numbers, I believe the input size is actually $Ndp$. But $O(\\log N)$ implies $O(\\log(Ndp))$, so there's no problem here even when $dp = \\omega(1)$ in $N$.\n6. Assuming $A_t, B_t, C_t, D_t$ are independent of the input sequence (and \"easily computable\"), it's easy to generalize the theorem to say that an SSM with $L$ layers, precision $p$ and hidden dimension $d$ is equivalent to an algorithm that uses $O(Lpd)$ space (i.e., you store hidden states $h_t^{(l)}$ of all layers $l$ at the current time step $t$ and the intermediate result $y_t^{(l_\\text{cur})}$ of the current layer $l_\\text{cur}$). So Theorem 4's statement that SSMs use log-space is actually just an artifact of $Lpd = O(\\log N)$ in the assumption of the (corrected version of the) theorem (see Question 3 above). So it's unclear what insight we get from the fact that SSMs are equivalent to log-space when $Lpd = O(\\log N)$. If $p, d = O(1)$ (i.e., the case of actual SSMs), then we get that linear SSMs are equivalent to algorithms that use $O(1)$ space, but does that mean that the decision problems that linear SSMs can solve must be regular languages? (A question of a similar nature: my computer has finite memory, so does that mean it can only decide regular languages?) On the other hand, if $p, d = O(\\mathrm{poly}(N))$, then we get that linear SSMs can be simulated by algorithms that use polynomial space, and we no longer get the takeaway that SSMs are limited. To summarize, the fact that the computational power of SSMs (as proven using the method in Theorem 4) varies widely based on what is assumed of the scaling of precision $p$ w.r.t. $N$ indicates a failure of \"SSM with precision $p = O(f(N))$\" as model to accurately capture the behavior of actual SSMs. Theorem 4 generalized would tell me that an SSM with precision $p = 16N$ can potentially solve P-complete problems and yet an SSM with $p = 64$ can only decide regular languages, but in practice there shouldn't be a difference in what these two classes of SSMs can do. (See below for what I think a theorem statement that actually formalizes the intuitive notion of \"SSMs can only compute problems in [complexity class]\" might look like.)\n\nHere's my suggestion for how to actually formalize \"SSMs only have _____ computational power\" into a theorem statement to replace the current Theorem 4.\n\nFirst, we need to define the inputs and outputs as actual strings, since members of $\\mathsf{FL}$ are functions $f : \\Sigma^* \\to \\Sigma^*$. So the input to the SSM is a sequence of tokens $w_1 \\ldots w_N$ that first get embedded into vectors $x_t \\in \\mathbb R^m$ ($t \\leq N$), and the output is an argmax applied on top of the last layer of $y_t$'s for $t > N$ until the <eos> token. (The $w_t$ for $t > N$ are the decoded $\\arg \\max_i (y_{t-1})_i$ as usual.) A basic formalization like this to properly define the inputs/outputs of an SSM is missing from the paper and should be added.\n\nNow, to prevent the issue in Question 6 above where the SSM's computational power ends up being limited by the finite precision in floating point computations, we really should assume infinite precision here. (So we're working with an idealized version of an SSM and not a real one.) And then we can ask about the computational power of an SSM with (given) hidden dimension $d$ and # layers $L$. So the theorem statement looks something like \"Functions $f : \\Sigma^* \\to \\Sigma^*$ that can be computed by an infinite-precision SSM with hidden dimension $d$ and # of layers $L$ are within the class _____.\"\n\nThe current proof of Theorem 4 doesn't work anymore, since directly carrying out the computations in the SSM would require infinite space. However, intuitively, SSMs should still be limited in their computational power for the following reason. Since input tokens are discrete, intuitively the spaces of $h_t$ and $y_t$ can, in some sense, be discretized into \"regions of equivalent behavior\". Thus, if we show that under certain conditions, the space of the hidden state can be divided into a finite number of regions of equivalent behavior, then the SSM is just a finite-state machine and the functions it computes are computable in $O(1)$ space.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Novel theoretical insight on the recently popular SSMs (especially in regards to their limited ability to do function composition), echoing similar previous work on Transformers. Experiments validate the theory.", "weaknesses": "1. The proof of Theorem 1 appears to rely on the specific format of the prompt (see Questions below).\n2. I have doubts about the correctness of Theorem 4's proof and I don't think the theorem statement itself properly formalizes the insight that it's trying to convey (see Questions below).\n3. It seems to me that the criticism in Question 6 below (i.e., that Theorem 4 really says \"SSMs' computational power is bounded by the amount of space used to represent floating points\") equally applies to the cited papers Merrill & Sabharwal 2023 and Merrill & Sabharwal 2024. Since Theorem 3 is based on the results of the latter paper, it relies on the problematic assumption that precision $p = O(\\log N)$. A consequence of this is that changing the assumption on how $p$ scales with $N$ even by a little bit will completely mess up the theorem statement, e.g., if $p = O(\\mathrm{poly}(n))$ then we can no longer say that SSMs can't solve these P-complete problems. (See Question 6 below for a more detailed discussion of this point as applied to Theorem 4.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VcKfWrMvkD", "reviewer": "Reviewer_BvEu", "summary": "This paper discusses the limitations of the reasoning abilities of SSMs and Transformers. Theoretically, it presents three theorems: (i) the inability of SSMs to efficiently perform function composition; (ii) Chain-of-thought helps yet with exponential increase in reasoning steps; and (iii) the inability of multi-layer SSMs to solve problems that are NL-Complete unless L = N. Empirically, the authors present experiments in qualitative examples of zero-shot inference, function composition, math and other reasoning tasks.", "questions": "See the weakness. I am happy to raise my score if the authors can address the concerns proposed by reviewers.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Originality: This paper precisely defines the problem and proposes new theorems showing new results.\n- Clarity and rigor: The theoretical and empirical sections are clearly structured, and concepts are clearly defined. \n- Significance: Reasoning is a crucial problem in this domain. The lower bound on CoT steps required for iterated function composition is an interesting result, showing the practical challenges in scaling up these techniques, which is valuable for the research community. I am not able to verify the proofs, though.\n- Empirical evaluation: The empirical results corroborate the theoretical claims effectively. The authors tested various composition tasks (function, spatial, temporal, and relational), presenting concrete evidence of performance degradation across different types of tasks.", "weaknesses": "Note: Unfortunately I am not a domain expert in theoretical computer science, and my evaluations are based on educated guess.\n\n- Could the authors provide an additional section on limitations (of this work per se) and future works, that practitioner may follow? For example, could the authors discuss more specific architectural modifications based on the existing results?\n- In practice, complicated reasoning tasks are often solved with (tree) search (cf., [alphaproof](https://deepmind.google/discover/blog/ai-solves-imo-problems-at-silver-medal-level/), [GPT-f](https://arxiv.org/pdf/2009.03393), [HyperTree Search](https://arxiv.org/pdf/2205.11491)), potentially with self-correction (cf., [Self-Correction](https://arxiv.org/pdf/2405.18634), [SCoRe](https://arxiv.org/pdf/2409.12917)), beyond naive stepwise chain-of0thought augmentation. Can the authors provide further discussions on this?\n\nReferences:  \n[1] Polu, Stanislas, and Ilya Sutskever. \"Generative language modeling for automated theorem proving.\" arXiv preprint arXiv:2009.03393 (2020).  \n[2] Lample, Guillaume, Timothee Lacroix, Marie-Anne Lachaux, Aurelien Rodriguez, Amaury Hayat, Thibaut Lavril, Gabriel Ebner, and Xavier Martinet. \"Hypertree proof search for neural theorem proving.\" Advances in neural information processing systems 35 (2022): 26337-26349.  \n[3] Wang, Yifei, Yuyang Wu, Zeming Wei, Stefanie Jegelka, and Yisen Wang. \"A Theoretical Understanding of Self-Correction through In-context Alignment.\" arXiv preprint arXiv:2405.18634 (2024).  \n[4] Kumar, Aviral, Vincent Zhuang, Rishabh Agarwal, Yi Su, John D. Co-Reyes, Avi Singh, Kate Baumli et al. \"Training language models to self-correct via reinforcement learning.\" arXiv preprint arXiv:2409.12917 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vtexSPlLfK", "reviewer": "Reviewer_Lnbo", "summary": "The core result of this paper is a proof that one-layer structured state space models cannot perform efficient function composition. The paper builds upon prior work from from Christos Papadimitriou in Peng et all who proposed the paradigm. The paper extends results to SSM models and shows that significant COT computation is required to achieve function composition in SSMs. Authors extend analysis to multi layer SSMsdemonstrating that the computation of an L-layer SSM on a prompt of length N can be carried out using O(L log N ) bits of memory, positioning SSMs within the complexity class L (logarithmic space). This implies that SSMs cannot solve problems that are NL-complete unless L = NL, which is widely believed to be false.", "questions": "Authors could also clarify the numerical experiments and their relationship to the main theorem with respect to layer number.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Paper is an important contribution as it extends rigorous complexity theory analysis of LLM model limitations to SSM models proving sharp results on resources required to execute function composition.", "weaknesses": "No real weakness. Potentially authors could spend more time comparing their results to Peng for readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YIRUIc6HXQ", "reviewer": "Reviewer_U9LY", "summary": "The authors investigate the computational limitations of structured state space models to perform function composition. They provide theoretical and empirical evidence for the infeasibility of these architectures to perform function composition over large domains.", "questions": "Minor comments and suggestions:\n\nThere is a formatting error causing the heading of section 7 to come too close to the previous paragraph.\n\nA summary figure of the empirical results could also be useful in the main manuscript if space limitations allow.\n\nThe “Implications for General Artificial Intelligence” paragraph seems more suited to the Conclusions section or a separate “Implications” section than to the “Related Work” section. An Implications section could also elaborate on the links between the formal proofs and the issues of practical interest.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Well written\n* Well referenced\n* Settles important questions about the limitations of current architectures of interest for sequence modeling.\n\nThis kind of theoretical work is very much needed.", "weaknesses": "* The main manuscript could use more background on communication complexity concepts and techniques, presented intuitively, to make the methodology and results more accessible to a general ML audience.\n* Computational complexity work often must deal with a gap between formal and practical problems (even if the work is conducted rigorously). The paper could use a discussion about this possible gap, the (non-)robustness of the results to closing this gap, and what kind of studies are needed to close this gap.\n\nSince there is still roughly 1 page of extra space before the manuscript reaches the page limit, it would be useful to have more background on the computational complexity concepts and techniques deployed in the proofs. This could include concepts and techniques from communication complexity, relevant problem classes and reducibilities, and the rationale that supports the proofs.\n\nComputational complexity work often must deal with objections related to the gap between theory and practice. It would be useful to elaborate on how these gaps might play out in this work, and what responses to possible objections might look like. For instance, what aspects of the formal definitions might be overly general with respect to a possibly more restricted practical setting? Might such a discrepancy between formalization and practical scenario account for the results? What kind of descriptive empirical work could be needed to close the gap between formal and practical problems?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)