Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory

## Abstract

Abstract Deep learning models have achieved significant success across various applications but continue to struggle with tasks requiring complex reasoning over sequences, such as function composition and compositional tasks. Despite advancements, models like Structured State Space Models (SSMs) and Transformers underperform in deep compositionality tasks due to inherent architectural and training limitations. Maintaining accuracy over multiple reasoning steps remains a primary challenge, as current models often rely on shortcuts rather than genuine multi-step reasoning, leading to performance degradation as task complexity increases.
Existing research highlights these shortcomings but lacks comprehensive theoretical and empirical analysis for SSMs. Our contributions address this gap by providing a theoretical framework based on complexity theory to explain SSMs’ limitations. Moreover, we present extensive empirical evidence demonstrating how these limitations impair function composition and algorithmic task performance. Our experiments reveal significant performance drops as task complexity increases, even with Chain-of-Thought (CoT) prompting. Models frequently resort to shortcuts, leading to errors in multi-step reasoning. This underscores the need for innovative solutions beyond current deep learning paradigms to achieve reliable multi-step reasoning and compositional task-solving in practical applications.

## 1 Introduction

Deep learning has achieved remarkable success across various applications, from natural language processing [, , ] and computer vision [, , ] to scientific computing [, ] and autonomous systems [, ].
The new frontier is general artificial intelligence. The goal is to design Large Language Models (LLM) that solve novel and difficult tasks that span mathematics, coding, vision, medicine, law, psychology and more at a close to human-level performance []. The mastery of function composition is essential for this objective as mathematical problem solving [], learning discrete algorithms [, ], logical reasoning [], and dynamic programming [] are all deeply compositional tasks. However, tasks requiring complex reasoning over sequences, particularly those involving function composition [] and compositional tasks [], remain challenging to deep learning models.

These tasks require the breakdown of problems into simpler sub-problems and composing the solutions of the subtasks. Despite their impressive capabilities on various language tasks, current Transformers models [] like the GPT-4o find it challenging to handle tasks needing deep compositionality []. We demonstrate, for instance, that GPT-4o only achieves about 27% accuracy on basic tasks like 4-by-3 digit multiplication. One approach at explaining this failure case of the transformer models is by their limitation to express simple kinds of state tracking problems []. For this reason, the Structured State Space Models (SSMs) [, ] have been introduced as an alternative to transformers, with the goal of achieving similar expressive power to RNNs for handling problems that are naturally sequential and require state-tracking. While SSMs have demonstrated impressive capabilities on various sequential tasks [, ], SSMs have similar limitations as Transformer models at solving function composition problems. We observe that for the same 4-by-3 digit multiplication task Jamba [] (SSM-Attention hybrid model) only achieves 17% accuracy.

Existing research has experimentally confirmed the inability of Transformers to perform function composition and compositional tasks [, ], leading to issues like hallucinations—where responses are incompatible with training data and prompts. Complexity theory analysis further reveals that Transformers belong to a weak complexity class, logspace-uniform TC^0 [], just like SSMs [], emphasizing their limitations. The impossibility of function composition for Transformers has been theoretically studied in []. A similar result for SSMs is presented in this paper.

Our contributions are twofold: first, we provide a theoretical framework using complexity theory to explain the limitations of SSMs in sequence modeling. Second, we offer extensive empirical evidence demonstrating these limitations across a variety of tasks. This evidence underscores how the inability to perform function composition critically impairs models in solving compositional and algorithmic tasks, resulting in reasoning errors and hallucinations.
Our key insight is the formal proof of SSMs’ inability to solve iterated function composition problems without a polynomially growing number of Chain-of-Thought (CoT) [] steps (Theorems [1](#Thmtheorem1) and [2](#Thmtheorem2)). CoT is a method where a model breaks down complex reasoning tasks into a sequence of intermediate steps or "thoughts," similar to how a human might solve a problem step-by-step. While CoT to some extent can enable complex problem-solving, it introduces a tradeoff between the model’s state size and the number of input passes required, leading to increased resource demands, which is not optimal.
Our experiments reveal significant performance degradation as task complexity increases, even with CoT prompting. These models often resort to learning shortcuts, leading to errors in multi-step reasoning processes. This behavior highlights their inability to integrate intermediate reasoning steps effectively, resulting in compounded errors, and underscores the need for innovative solutions beyond current deep learning paradigms.

## 2 Background

For two natural numbers $n\leq m$, we denote $[n]=1,2,\dots n$ and $[n,m]=n,n+1,\dots,m$, with $[0]=[n,n-1]=\emptyset$. We refer to the number of bits used in each computation as computational precision $p$. Given two domains $B,C$, we denote by $B^{C}$ set of all functions from the $B$ to $C$.

###### Definition 1 (SSM layer) .

Given an input sequence $\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{n}\in\mathbb{R}^{m}$, an SSM layer $\mathcal{L}$ is defined in terms of a series of matrices $\boldsymbol{A}_{t}\in\mathbb{R}^{d\times d}$, $\boldsymbol{B}_{t}\in\mathbb{R}^{d\times m}$, $\boldsymbol{C}_{t}\in\mathbb{R}^{m\times d}$, and $\boldsymbol{D}_{t}\in\mathbb{R}^{m\times m}$ for $t\in[n]$. $\mathcal{L}$ defines a sequence of states $\boldsymbol{h}_{1},\dots,\boldsymbol{h}_{n}\in\mathbb{R}^{d}$ as

$$ $\boldsymbol{h}_{t}=\boldsymbol{A}_{t}\boldsymbol{h}_{t-1}+\boldsymbol{B}_{t}\boldsymbol{x}_{t};$ $$

and outputs the sequence $\boldsymbol{y}_{1},\dots,\boldsymbol{y}_{n}\in\mathbb{R}^{m}$ as

$$ $\boldsymbol{y}_{t}=\boldsymbol{C}_{t}\boldsymbol{h}_{t}+\boldsymbol{D}_{t}\boldsymbol{x}_{t}.$ $$

Generally, the matrices $\boldsymbol{A}_{t}=\boldsymbol{A}(\boldsymbol{x}_{t})$, $\boldsymbol{B}_{t}=\boldsymbol{B}(\boldsymbol{x}_{t})$, $\boldsymbol{C}_{t}=\boldsymbol{C}(\boldsymbol{x}_{t})$, and $\boldsymbol{D}_{t}=\boldsymbol{D}(\boldsymbol{x}_{t})$ are functions of the input vector $\boldsymbol{x}_{t}$ for each $t\in[n]$.
In the special case when $\boldsymbol{A}_{t}$, $\boldsymbol{B}_{t}$, $\boldsymbol{C}_{t}$, and $\boldsymbol{D}_{t}$ are independent from the input sequence $\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{n}$, we call $\mathcal{L}$ a *linear SSM layer*. Moreover, we call $d$ the embedding dimension.

###### Definition 1 (SSM layer) .

## 3 Function Composition Requires Wide Models

The function composition problem has been introduced in [] to provide a theoretical understanding of the causes for the hallucination of Transformer models. The aim is to evaluate the model’s capability to combine relational information in the data to understand language, the core competence of large language models. Indeed to correctly answer questions like *’what is the birthday of Frédéric Chopin’s father?’* given the information that *’the father of Frédéric Chopin was Nicolas Chopin’* and that *’Nicolas Chopin was born on April 15, 1771’*, the model needs to be able to compose the functions *’birthday-of’* and *’father-of’* [], [].

Next, we give a precise formulation of the *function composition problem* due to []. Consider two functions, $g$ mapping a domain $A$ to a domain $B$, and $f$ mapping $B$ to another domain $C$. These functions will be described in a prompt $X$. The $N$ tokens of $X$ are divided into three parts:

- 1.
the first part describes the function $g$ through $|A|$ sentences in simple, unambiguous language separated by punctuation, e.g. *’the father of Frédéric Chopin is Nicolas Chopin’*,
- 2.
the second part consists of $|B|$ sentences describing the function $f$, e.g. *’the birthday of Nicolas Chopin is April 15, 1771’*,
- 3.
the third part is the query question asking for the value of $f(g(x))$ for some specific $x\in A$.

In this section, we discuss the theoretical limitations of SSMs for solving the function composition problem.

###### Theorem 1 .

Consider a function composition problem with input domain size $|A|=|B|=n$, and an SSM layer $\mathcal{L}$ with embedding dimension $d$ and computation precision $p$. Let $R=n\log n-(d^{2}+d)p\geq 0$, then the probability that $\mathcal{L}$ answers the query incorrectly is at least $R/(3n\log n)$ if $f$ is sampled uniformly at random from $B^{C}$.

The proof is based on a reduction to a famous problem in communication complexity [], [].
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 to Xavier. Faye knows a function $f:[n]\mapsto[n]$ and the argument $x\in[n]$, Grace knows a function $g:[n]\mapsto[n]$ and the argument $x$, while Xavier only knows the argument $x\in[n]$. The goal is for Xavier to compute the value of $f(g(x))$ minimizing the total number of bits communicated from Faye to Xavier and from Grace to Xavier.

We report here a lemma from [] which gives a hardness result for the problem above.

###### Lemma 1 (Lemma 1 from [ 30 ] ) .

Consider the problem described above, if fewer than $n\log n$ bits are communicated by Faye to Xavier, then Xavier cannot know the value $f(g(x))$. In particular, if only $n\log n-R$ bits are communicated for some $R\geq 0$, then the probability that the composition is computed incorrectly is at least $R/(3n\log n)$ if $f$ is sampled uniformly at random from $B^{C}$.

Now we prove the theorem based on the lemma above.

###### Proof of Theorem 1 .

In order to establish the bound on $q$, we give a reduction of the communication problem above to the function composition problem. Let $\mathcal{L}$ be a SSM layer that can solve the function composition problem with probability $q$.

Suppose that we have Faye, Grace, and Xavier as in the settings above and Xavier wants to find the value $f(g(x))$. We construct the following prompt: for $i\in[1,n]$ let $\boldsymbol{x}_{i}$ be the token *’$g$ applied to $i$ is $g(i)$’*, where the information is provided by Grace, and for $i\in[n+1,2n]$ let $\boldsymbol{x}_{i}$ the token string *’$f$ applied to $i$ is $f(i)$’*, where the information is provided by Faye. Xavier provides the last token string $\boldsymbol{x}_{2n+1}=$ *’what is the value of $f(g(x))$’*. Since the SSM layer $\mathcal{L}$ can solve the composition task with probability $q$, we have that

$$ $\boldsymbol{y}_{2n+1}=\boldsymbol{C}_{2n+1}\boldsymbol{h}_{2n+1}+\boldsymbol{D}_{2n+1}\boldsymbol{x}_{2n+1}=f(g(x))$ $$

with probability $q$.

But this allows us to construct the following communication protocol. Since Grace knows $g$, she knows the values of $\boldsymbol{x}_{i}$ for $i\in[1,n]$ and she iteratively computes

$$ $\boldsymbol{h}_{i}=\boldsymbol{A}_{i}\boldsymbol{h}_{i-1}+\boldsymbol{B}\boldsymbol{x}_{i},$ $$

and then sends $\boldsymbol{h}_{n}$ to Xavier. On the other hand, Faye knows $f$ and hence the values of $\boldsymbol{x}_{i}$ for $i\in[n+1,2n]$, she computes the matrix

$$ $\mathcal{A}=\prod_{j=n+1}^{2n}\boldsymbol{A}_{j}$ $$

and the vector

$$ $\boldsymbol{b}=\sum_{i=n+1}^{2n}\left(\prod_{j=n+1}^{2n-i}\boldsymbol{A}_{j}\right)\boldsymbol{B}_{i}\boldsymbol{x}_{i}$ $$

and she sends them to Xavier.
At this point, Xavier computes

$$ $\boldsymbol{h}_{2n+1}=\boldsymbol{A}_{2n+1}\cdot(\mathcal{A}\cdot\boldsymbol{h}_{n}+\boldsymbol{b})+\boldsymbol{B}_{2n+1}\boldsymbol{x}_{2n+1}.$ $$

and find the value of $f(g(x))$ with probability $q$ by computing $\boldsymbol{y}_{2n+1}=\boldsymbol{C}_{2n+1}\cdot\boldsymbol{h}_{2n}+\boldsymbol{D}_{2n+1}\cdot\boldsymbol{x}_{2n+1}$. The total number of bits of communication between Faye and Xavier is $(d^{2}+d)\cdot p$. By Lemma [1](#Thmlemma1), it follows that $q\leq R/(3n\log n)$.
∎

###### Theorem 1 .

###### Lemma 1 (Lemma 1 from [ 30 ] ) .

###### Proof of Theorem 1 .

## 4 Many Thought Steps are Needed

A chain of thought (CoT) is a series of intermediate natural language reasoning steps that lead to the final output. In this section, we focus on language models with the ability to generate a similar chain of thought— a coherent series of intermediate reasoning steps that lead to the final answer for a problem. In [], it was observed that CoT can mitigate the problem of hallucinations by encouraging the LLM to generate prompts which break down the task into smaller steps eventually leading to the correct answer. In this section, we prove that in general many CoT steps are needed to break down compositional tasks.

We start the discussion with the formal definition of an SSM with $k$ CoT-steps. It adapts the definition for the Transformer model of [] to the case of SSMs.

###### Definition 2 (SSM with CoT) .

Let $\phi:(\mathbb{R}^{m})^{*}\rightarrow\mathbb{R}^{m}$ be a function mapping a prefix of tokens to a new token. The function $\phi$ is parametrized by a SSM layer $\mathcal{L}$.

Given an input sequence
$\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{n}\in\mathbb{R}^{m}$, we call

$$ $\phi_{k}(\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{n})=\phi_{k-1}(\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{n})\cdot\phi(\phi_{k-1}(\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{n}),\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{n}),$ $$

where $\phi_{1}(\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{n})=\phi(\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{n})$ and $\cdot$ denotes concatenation, the output of the SSM layer $\mathcal{L}$ with $k$ CoT-steps.

In this section, we want to prove that, while this procedure could help SSM layers with compositional tasks, it might require a large number of chain of thought steps in order to be effective.
In particular we focus on the iterated function composition problem and show a lower bound on the number of CoT steps needed by a SSM layer in order to solve this problem correctly.

In the *iterated function composition* problem we are given $k$ functions $f_{1},f_{2},\dots,f_{k}:[n]\mapsto[n]$, and we need to calculate $f_{k}(f_{k-1}(\dots f_{2}(f_{1}(x))\dots))$ for $x\in[n]$. Here we restrict to the case when $f_{1}=f_{2}=\dots=f_{k}$, we define $f^{(k)}(x):=f(f(\dots f(x)))$, and we call this *$k$-iterated function composition* problem.

###### Theorem 2 .

Consider an iterated composition problem with domain size $n$, computation precision $p$, and embedding dimension $d$. An SSM layer requires $\Omega(\frac{\sqrt{n\log n}}{dp})$ CoT steps for answering correctly iterated function composition prompts.

The proof relies on a reduction of the iterated function composition problem to the pointer chasing problem [], a classical problem in communication complexity. In the *$k$-steps pointer chasing* problem, we have two agents dubbed Alice and Bob, Alice knows a function $f_{A}:[n]\mapsto[n]$ and Bob knows a function $f_{B}:[n]\mapsto[n]$. We then define the pointers

$$ $z_{1}=1,\quad z_{2}=f_{A}(z_{1}),\quad z_{3}=f_{B}(z_{2}),\quad z_{4}=f_{A}(z_{3}),\quad z_{5}=f_{B}(z_{4}),\quad\dots.$ $$

The communication proceeds for $2k$ rounds, with Alice starting. The goal is for Bob to output the
binary value of $z_{2k+2}\mod 2$. We prove in the appendix [A](#A1), that a SSM layer with $R$ CoT steps solving the iterated function composition problem can be used to design a communication protocol for the pointer chasing problem where the number of transmitted bits scales with $R$. The next fundamental Lemma in communication complexity gives a lower bound on the number of bits that need to be communicated in any such communication protocol and thus allows to derive the lower bound on the CoT steps.

###### Lemma 2 (Theorem 1.1 [ 43 ] ) .

Any randomized protocol for the $k$-steps pointer chasing problem with error probability $1/3$ under the uniform distribution must involve the transmission of at least $n/(2000k)-2k\log n$ bits.

###### Definition 2 (SSM with CoT) .

###### Theorem 2 .

###### Lemma 2 (Theorem 1.1 [ 43 ] ) .

## 5 SSM’s Capability to Reason Is Limited by LOGSPACE

In [], it is suggested to an analyse the computational capability of LLMs on the following three computational problems. In fact, the empirical compositional tasks, studied in later sections, multiplication of multi-digit integers, dynamic programming and logic puzzles such as “Einstein’s Riddle” can be expressed in terms of these computational problems[].

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\subseteq S\times S$. For a given initial set $I\subseteq S$ and a final set $F\subseteq S$, answer the question whether there are elements $a_{1},a_{2},\ldots,a_{k}\in S$ such that (a) $a_{0}\in I$, (b) $a_{k}\in F$, and (c) for all $j$ such that $0<j\leq k,\left(a_{j-1},a_{j}\right)\in D$.

Logical reasoning: Logic puzzles like ’Einstein’s Riddle’ can be typically formulated as instances of satisfiability (or SAT). This problem is NP-complete. However, most common-sense reasoning can be expressed by one of the three tractable special cases of SAT: 2-SAT, Horn SAT, Mod $2$ SAT.

In [], it was noted that since derivability, 2-SAT, Horn SAT, and circuit evaluation are all NL-complete and the Transformer model lies in the complexity class log-uniform $\textbf{TC}^{0}\subseteq$ L, these problems cannot be solved by a Transformer model provided $\textbf{NL}\neq\textbf{L}$ (which is a widely believed hypothesis in computational complexity). For Mod 2 SAT, the result is true provided the weaker statement $\textbf{L}\neq\text{Mod }2\textbf{ L}$. Very recently in [], it was established that linear and S6- SSMs [] are also part of the complexity class log-uniform $\textbf{TC}^{0}$, which yields the following theorem similar to the case of transformers.

###### Theorem 3 .

The four problems of Derivability, 2-SAT, Horn SAT, and Circuit evaluation cannot be solved by linear or S6- SSMs provided $\mathbf{L}\neq\mathbf{NL}$. For Mod 2 SAT, the result is true provided the weaker statement $\mathbf{L}\neq\text{Mod }2\mathbf{L}$ holds.

In fact the argument in [], should also establish that linear and S6- SSMs with $\log(n)$ CoT steps, where $n$ is the size of the input, are still part of the complexity class L. This allows to extend the theorem [3](#Thmtheorem3) even to the case of linear and S6- SSMs with $\log(n)$ CoT steps.

###### Theorem 3 .

## 6 Experiments

To evaluate the inability of various sequence models in addressing function composition tasks (Sec. [6.1](#S6.SS1)a), we examine three axes of composition: spatial, temporal, and relational. This evaluation is conducted using four datasets specifically designed to test function composition (Par. [6.1](#S6.SS1.SSS0.Px3)b). Subsequently, we proceed to compositional tasks involving multi-digit multiplication, dynamic programming, and Einstein’s puzzle (Par. [6.1](#S6.SS1.SSS0.Px4)c). We investigate the effects of CoT prompting (Sec. [6.2](#S6.SS2)) and conduct a thorough error analysis to understand the failure points and underlying reasons for this erroneous behaviour (Sec. [6.3](#S6.SS3)).

We conduct GPT experiments using the ChatGPT API [], while evaluations of other models are performed on 2x A100 80 GB GPUs. Each task is evaluated three times with typically 500 test samples per evaluation, unless otherwise specified, to ensure consistency and minimize variance.

### 6.1 Function composition and compositional tasks

In the context of Large Language Models (LLMs), compositional tasks differ from function composition. Function composition $f_{K}(f_{K-1}(\ldots(f_{1}(x))))$ is a mathematical process where the output of one function serves as the input for another across multiple functions $f_{1},f_{2},\ldots,f_{K}$. Conversely, compositional tasks in LLMs involve breaking down complex inputs into simpler parts and integrating the results to generate an 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 [, ] and demands additional competencies such as 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 []. For instance, if an SSM-powered LLM cannot evaluate $f(g(x))$, 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 of 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 on understanding the connections between entities, such as those found in a genealogy tree.

#### Number of Parameters

We conducted experiments using Jamba [] (joint Mamba and Attention) with 7B parameters, Mamba [] with 2.8B parameters, S4-H3 [, ] with 2.7B parameters, GPT-4 [], and GPT-4o models. Qualitative results are presented in the Fig. [1](#S6.F1). As illustrated in Fig. [1](#S6.F1), all models failed to correctly answer questions across the three composition axes.

Figure: Figure 1: Qualitative example of zero-shot inference on prominent SSM and Attention-based 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 [], 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 on 500 samples.

#### Composition datasets

Math-QA dataset, derived from [], 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 [] dataset features 250 Boolean expressions that the model must evaluate. In Temporal-NLI [] dataset each sample consists of a premise (e.g., "They got married on Saturday") and a hypothesis (e.g., "They got married before Friday"), requiring the model to determine if the relationship is entailment, contradiction, or neutral. SpaRTUN [] 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).

**Table 1: Performance of Attention, SSM and Attention-SSM based models on various function composition tasks involving logical expressions, temporal reasoning, spatial reasoning, and math tasks.**
|  | GPT-4o [] | GPT-4 [] | Jamba [] | Mamba [] | S4-H3 [, ] |
| --- | --- | --- | --- | --- | --- |
| Math-QA [] | $51.8\%$ | $51.0\%$ | $42.2\%$ | $35.0\%$ | $28.6\%$ |
| BIG-Bench Hard [] | $56.8\%$ | $58.4\%$ | $78.2\%$ | $67.0\%$ | $60.6\%$ |
| Temporal-NLI [] | $79.4\%$ | $77.2\%$ | $69.8\%$ | $59.2\%$ | $54.6\%$ |
| SpaRTUN [] | $80.8\%$ | $61.4\%$ | $50.8\%$ | $42.2\%$ | $35.2\%$ |

The results presented in Tables [2](#S6.T2) and [2](#S6.T2) highlight several key observations regarding the performance of various models across different composition tasks. Notably, Mamba [] consistently outperforms the S4-H3 [, ] 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, it 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 [] benchmark. This indicates that even state-of-the-art 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 simpler composition tasks, we now examine their performance on more complex compositional tasks. Given their proven inability to perform function composition, as established in Theorem [1](#Thmtheorem1), 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 puzzle.

For the multi-digit multiplication task, we generate question-answer pairs such as "What is 5 times 90?" with the answer being "450". This task involves multiplying two numbers, $x=(x_{1},x_{2},\dots,x_{k})$ and $y=(y_{1},y_{2},\dots,y_{k})$, where each number can have up to $k$ digits. Consequently, there are $9\times 10^{(k-1)}$ possible combinations for each number. In our experiments, we set $k$ to 5 and found that both Attention and SSM-based models are unable to solve the 5-by-5 digit multiplication task, even in the case of GPT-4o with CoT prompting (A- [12](#A3.F12)).

Figure: Figure 2: Jamba [] performance on multiplication, DP and puzzle tasks. For DP various models are shown. All struggle with compositional tasks, especially for larger input size.
Refer to caption: /html/2405.16674/assets/x1.png

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 []: Given a sequence of integers, find a subsequence with the highest sum such that no two numbers in the subsequence are adjacent in the original sequence. This relaxation can be solved in $O(n)$ time using DP. For our experiments, we restrict each integer to the range $[-5,5]$ and follow the generation steps as in [], with input list containing from 2 to 6 elements. Prompting details are shown in the A-[B.3](#A2.SS3).

Einstein’s puzzle is a well-known logic puzzle commonly used as a benchmark for solving constraint satisfaction problems []. It involves a series of houses with various attributes, and the objective is to determine which attributes correspond to each house by interpreting a set of predefined natural language clues or constraints. The solution to the puzzle is represented as a matrix of size $H\times 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](#A2.SS2).

### 6.2 CoT experiments

Next, we evaluate how the popular chain-of-thought (CoT) prompting method [] affects the performance of GPT-4o [], Jamba [], Mamba [] and S4-H3 [] models on compositional tasks from Sec. [6.1](#S6.SS1). CoT improves the performance, but does not solve the task. Details of the experiments and examples of full prompts can be found in the A-[C](#A3).

### 6.3 Error analysis

We focus on graph analysis of errors, with emphasis on 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 [, , ].

#### Computation Graph

To study the propagation of errors and its dependency on input size, we define $A$ as a deterministic algorithm (function), and $\mathcal{F}_{A}$ as the set of primitives (functions) the algorithm employs during execution. Given inputs $\mathbf{x}$ to the algorithm $A$, we define the static computation graph of $A(\mathbf{x})$, denoted as $G_{A(\mathbf{x})}$, as $G_{A(\mathbf{x})}=(V,E,s,op)$, a directed acyclic graph.

Nodes $V$ represent all variable values during $A$’s execution, where each node $v\in V$ has an associated value $s(v)\in\mathbb{R}$. Edges $E$ represent function arguments involved in computations: for each non-source node $v\in V$, let $U=\{u_{1},\ldots,u_{j}\}\subset V$ be its parent nodes. Then, $s(v)=f(u_{1},\ldots,u_{j})$ for some $f\in\mathcal{F}_{A}$. Since each node $v$ is uniquely determined by the computation of a single primitive $f$, we define $op:V\rightarrow\mathcal{F}_{A},op(v)=f$ as the operator function that yields $s(v)$.
Let $S\subset V$ be the source nodes of $G_{A(\mathbf{x})}$, and without loss of generality, let $o\in V$ be its sole leaf node. By definition, $S\equiv\mathbf{x}$ and $A(\mathbf{x})=s(o)$, representing the input and output of $A$, respectively.
To evaluate a language model’s ability to follow algorithm $A$, we must linearize $G_{A(\mathbf{x})}$ (arrange the nodes in a linear sequence that respects the dependencies). This means if a node $u$ is a parent of node $v$, the $u$ should appear before $v$ 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 as defined by the algorithm $A$.

Figure: Algorithm 1 Multiply two numbers
Refer to caption: /html/2405.16674/assets/x4.png

To instantiate $G_{A(\mathbf{x})}$, let $\mathcal{F}_{A}=\{\text{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 $v$ are partial results generated during execution of the long-form multiplication algorithm (see Fig. [3](#S6.F3.3)). Corresponding algorithm is on the left of the Fig. [3](#S6.F3.3) - Alg. [1](#alg1).

#### Error propagation

We investigate the types of errors encountered by SSMs. Specifically, Fig. [5](#S6.F5) illustrates the errors produced by the S4-H3 model [, ]. The figure reveals a prevalence of local errors, where the immediate outputs are incorrect despite the correctness of ancestor outputs. Propagation errors occur when the model generates correct outputs from incorrect ancestor values—e.g., in Fig. [5](#S6.F5), the computation 3 + 4 = 7 is correct, but the value 3 results from a local error. Our analysis reveals that propagation errors are 2-4 times more frequent than local errors, consistent with findings by [] for Transformers. This indicates that SSM-based models, like Transformers, can handle single-step reasoning well due to pretraining memorization but struggle with multi-step reasoning and planning. Consequently, these models excel at local tasks but fail to integrate steps into coherent global reasoning, leading to error propagation.

Figure: Figure 4: Error Propagation. Carry operation outputs number 3 instead of 2 from node ’27’, and that error is further propagated, yielding incorrect solution in the middle digit, although all other steps were done right.
Refer to caption: /html/2405.16674/assets/x5.png

#### SSMs learn shortcuts

The performance of SSMs provides valuable insights into their behavior. These models often predict partially correct answers even when the overall response is incorrect. For example, using Mamba [] for 2-by-2 digit multiplication, the first and last digits are usually accurate. In larger multiplications, the first two and last two digits tend to be correct. Using Relative Information Gain (RIG) analysis [], we find that SSMs learn shortcuts, performing fewer operations (illustrated by the red and green subgraphs in Fig. [5](#S6.F5)). This allows them to frequently predict peripheral digits correctly. For instance, to compute the last digit, the model multiplies 8 and 5, carrying 0 to the end, mimicking human multiplication and easily predicting the last digit accurately. RIG analysis reveals a 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.

These models leverage task distribution shortcuts to guess partial answers without full multi-step reasoning. Increasing the number of Chain-of-Thought (CoT) steps doesn’t always improve results, especially for larger input sizes (deeper computation graphs). If the model encounters relevant subgraphs during training, its inference seems highly compositional but is based on shortcuts [, , , ]. These experiments indicate that when an output element heavily relies on a 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 [].

### 6.4 Learning Algorithmic Compositions

Finally, we conduct a comprehensive analysis of the capabilities of SSM-based models, along with GPT-4o [], to "learn" discrete algorithms. This analysis is performed using two tasks that require the composition of 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 []. This suggests that, within the framework of in-context learning, SSM and Transformer-based models fail to attain compositional learning when constrained to a fixed number of samples. Details in the A-[D](#A4).

## 7 Related work

#### Limitations in Function Composition and Reasoning

Recent studies have underscored the limitations of deep learning models, particularly Transformers in handling tasks requiring deep compositionality and multi-step reasoning [, ]. These tasks are crucial in applications like mathematical problem-solving [], algorithm learning [], logical reasoning [], and dynamic programming [].
Transformers, despite their capabilities, have been shown to struggle with function composition, which is essential for understanding relational information in data []. Research has highlighted the architectural and training limitations that prevent these models from maintaining accuracy over multiple reasoning steps, leading to issues like hallucinations []. Studies by [] and [] have identified that both Transformers and SSMs belong to weak complexity classes, such as logspace-uniform TC^0, which limits their abilities. However, SSMs were not investigated theoretically and experimentally in terms of ability to perform function composition and compositional tasks, which is our contribution.

#### Chain-of-Thought (CoT) Prompting

The Chain-of-Thought (CoT) prompting method has been proposed as a potential solution to improve reasoning capabilities in large language models by breaking down complex tasks into smaller, intermediate steps []. This approach aims to mitigate hallucinations and improve multi-step reasoning. However, our research indicates that even with CoT prompting, current models remain inadequate for solving deeply compositional tasks [].

## 8 Conclusions

In this paper, we have rigorously explored the limitations of deep learning models, particularly Structured State Space Models (SSMs) and Transformers, in handling tasks requiring deep compositionality and multi-step reasoning. Through a blend of theoretical insights and empirical analysis, we demonstrated that these models inherently struggle with function composition and compositional tasks due to their architectural constraints.

## 9 Limitations

Our study primarily focuses on the theoretical and empirical limitations of SSMs and Transformers in sequence modeling and compositional tasks. While we have demonstrated these inherent limitations, our analysis does not provide a solution but rather establishes the existence of these issues both theoretically and practically. Future research should explore alternative architectures and broader applications to better understand and address these limitations.

## 10 Acknowledgment

This work was supported by the European Research Council (ERC) under grant agreement No. 864042 (AGILEFLIGHT).

## Appendix A Proof of Theorem 2

Before we begin with the actual proof, let us introduce some notation. We note that $\phi_{k}$ is a string of $k$ tokens of $\mathbb{R}^{m}$. Moreover, to compute the new token $\phi(\phi_{k-1}(\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{n}),\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{n})$ the SSM layer $\mathcal{L}$ computes $n+(k-1)$ hidden states. We denote the $i$-th hidden state by $\phi_{k,i}(\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{n})$.

###### Proof of Theorem 2 .

The proof is similar to the proof of Theorem 2 in [].
We reduce the pointer chasing problem to the iterated composition problem with CoT prompts. In particular, we show that if the SSM $\mathcal{L}$ can solve the $k$-iterated function composition problem with $R$ CoT steps, then we can construct a protocol solving the $(k-1)$-steps pointer chasing problem using $2Rdp$ bits of communication.

Fix a $(k-1)$-steps pointer chasing problem for the function $f_{A},f_{B}:[n]\mapsto[n]$. Define the function $f:[2n]\mapsto[2n]$ as

$$ $f(i)=\begin{cases}f_{A}(i)+n,&i\in[1,n];\\ f_{B}(i-n),&i\in[n+1,2n].\end{cases}$ $$

We point out that $f^{(k)}(i)=(f_{B}\circ f_{A})^{(k)}(i)$. Consider the $k$-iterated function composition problem for $f$ and suppose that there exists a SSM $\mathcal{L}$ that solves it using $R$ CoT steps.

We construct the following prompt: for $i\in[1,n]$ let $\boldsymbol{x}_{i}$ be the token *’$f$ applied to $i$ is $f(i)$’*, where the information $f(i)$ is provided by Alice, and for $i\in[n+1,2n]$ let $\boldsymbol{x}_{i}$ the token string *’$f$ applied to $i$ is $f(i)$’*, where the information $f(i)$ is provided by Bob. The last token string $\boldsymbol{x}_{2n+1}$ is given by *’what is the value of $f^{(k)}$ applied to $x$’*. Since the SSM layer $\mathcal{L}$ can solve the $k$-iterated function composition task with $R$ CoT steps, we have that $\phi_{R}(\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{2n})$ is the right answer for $f^{k}(x)$. We will use this fact to construct a communication protocol transmitting at most $2\cdot Rdp$ bits. The communication protocol lasts for $R$ rounds.

In the r-th round Alice computes $\phi_{r,n+k}(\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{2n})$ from $\phi_{r-1}(\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{2n})$ (where $\phi_{0}(\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{2n})$ is the empty string of tokens) and $\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{n}$ and communicates it with Bob. Bob on the other hand computes $\phi_{r}(\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{2n})$ from $\phi_{r,n+k}(\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{2n})$ and $\boldsymbol{x}_{n+1},\dots,\boldsymbol{x}_{2n}$ 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 $\phi_{R}(\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{2n})$. 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 are $2Rdp$. In conclusion, we fix $k=\frac{1}{100}\sqrt{\frac{n}{\log n}}+1$ and by Lemma [2](#Thmlemma2) we get that $2Rdp\geq n/(2000k)-2k\log n$ which gives $R\geq\frac{3}{100}\frac{\sqrt{n\log n}}{dp}$
∎

###### Proof of Theorem 2 .

## Appendix B Compositional Tasks Details

### B.1 Multiplication

We show examples of few-shot and CoT prompting methods for multiplication task (Figs. [6](#A2.F6) & [7](#A2.F7)).

Figure: Figure 6: Example prompt for the multiplication task used for the few-shot prompting.

Figure: Figure 7: A sample scratchpad for the multiplication task.

### B.2 Einstein’s Puzzle

#### Data Construction

Following [], 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 a red color."). We then create a basic and clear set of clue types:
1. found_at: For example, “Alice lives in House 2.”
2. same_house: For example, “The person who is a cat lover lives in the house that has a red color.”
3. direct_left: For example, “The person who has a dog as a pet lives to the left of the person who lives in a 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_at, left_of (not necessarily directly left), and two_house_between. These harder clues are 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 [] to generate the computation graph. Our algorithm follows a basic greedy principle: it applies the minimum number of rules necessary to solve any cell. Specifically, if a 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 [8](#A2.F8) shows an example of a scratchpad.

Figure: Figure 8: A sample scratchpad for the Einstein’s puzzle task.

### B.3 Dynamic Programming

We show examples of zero/few-shot and CoT prompting methods for dynamic programming task (Figs. [9](#A2.F9) & [10](#A2.F10)), following [].

Figure: Figure 9: Example prompt for the DP task, used for zero-shot and few-shot settings.

Figure: Figure 10: A sample scratchpad for the DP task.

## Appendix C Details of CoT experiments

### C.1 Main CoT experiments

We plot the performance of Jamba [] on multiplication and puzzle tasks, and various models on DP task after using CoT.

Figure: Figure 11: Jamba’s [] 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.
Refer to caption: /html/2405.16674/assets/x7.png

The leftmost heatmap on Fig. [11](#A3.F11) represents the Jamba [] model’s multiplication performance, showing a consistent high performance for multipliers of 1 and 2, but a noticeable decline as the multipliers increase, particularly beyond 3. The middle heatmap compares the performance of four models—GPT-4o [], Jamba [], Mamba [], and S4-H3 [, ]—on dynamic programming tasks with CoT prompting []. GPT-4o [] 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 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 [] generally enhances model performance, its effectiveness varies significantly across different models and task complexities.

### C.2 Performance of other models on multiplication and puzzle tasks

We observe the same pattern on both tasks, for all the models - Figs. [12](#A3.F12) & [13](#A3.F13). GPT-4o [] is always the best model, followed by Jamba [], then Mamba [], then S4-H3 [, ]. While CoT helps, it is not enough to solve the task.

Figure: Figure 12: Comparison of different models on multiplication task using CoT.
Refer to caption: /html/2405.16674/assets/x10.png

Figure: Figure 13: Comparison of different models on puzzle task using CoT.
Refer to caption: /html/2405.16674/assets/x13.png

### C.3 Few-shot prompting multiplication results

We investigate whether few-show prompting (giving a model few input/output pairs) and then asking for the answer to the new problem helps. Fig. [14](#A3.F14) shows the results, and consistently CoT outperforms Few-shot prompting, and Few-shot prompting outperforms Zero-shot prompting.

Figure: Figure 14: Comparison of different models on multiplication task using few-shot prompting.
Refer to caption: /html/2405.16674/assets/x16.png

## Appendix D Algorithmic Compositions

Following [], we evaluate the models using the PE’s Neighbour (PEN) task. This task involves navigating from one word to the next based on a specified matching criterion and outputting all the neighbours encountered along the way. The PEN task, inspired by [] and rooted in the Pointer Value Retrieval framework [], 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 neighbours), and (iv) PE Verbose (PEV) - outputting both the words of the matching sequence and their neighbours.
These sub-tasks are essential because, to predict the next word, the model must: take the current word in the answer, obtain the left neighbour (learned in Reverse Copy), match it (learned in PE), and then obtain the right neighbour (learned in Copy). PEV is considered a sub-task because it requires solving the same problem as PEN but with the added complexity of providing both matching words and their neighbours. PEN, on the other hand, only requires outputting the neighbours. For accurate next-token prediction the model cannot simply replicate the last matching sequence word from the previous answers, it must first infer it from the neighbour.
To increase the task’s complexity, "attention traps" or "doppelgangers" are introduced. These traps create additional matching possibilities by allowing each neighbour to match two other words, thus tempting the model to match from the neighbour 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 neighbour, 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 a non-linearity. For this task, we omit any attention traps, as there are no neighbours involved. In the A- [D](#A4) we show concrete prompt examples and share the code.

We conducted extensive evaluations on 500 test samples using various models under different conditions: zero-shot, few-shot (providing a limited number of input-output pairs), and CoT prompting []. Remarkably, none of the models, including the state-of-the-art GPT-4o [], succeeded in solving the PEN task []. Typically, models correctly generated the initial strings but then halted prematurely or produced random strings. The same pattern of failure was 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 GPT-4o is attributed to its substantially larger parameter count compared to SSM-based models ([6.1](#S6.SS1.SSS0.Px2)).

Figure: Table 3: Model Accuracy for PEN task

In the following subsections we focus on showing the prompts in few-shot and CoT settings for PEN and PER Multi tasks. Moreover, we show the code we used to generate the samples.

### D.1 Prompts for SSM and Attention-based models for PEN task

Figure: 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-match the respective token to do the matching operation.

Prompt for the PEN task with few-shot CoT examples and a description.
I give you a sequence of words. Each word has four characters plus a middle, words are separated by spaces. Start with the leftmost word. Output its neighbour. Then, match the last two characters of the current word (i.e. not the neighbour) to the word starting with those two characters. Again, output the neighbour. Do this until your current word (not the neighbour) has no match anymore.
Example: xh jz qw4se zs1qh xv4vn me3af vs1nh ok3ks sn6iv qh1va da5gy ks1ew tw7ik em5zs xs5qu ft3me gt3bc em3zs zn5qv ks5ew by7kn me7af je0wt cb0ft pw6hg rk7cb dv2sn ew3rk yg1by va1cq qu7fp qh4va vn5zn ok1ks cc7tw rk0cb bc7qi jz7em qz2cs ew6rk qv6gt ft7me fp1qw sa6ok sd7pn jz3em wi3da cq7sa iv0vl zs7qh vl2kc va5cq fe5wi xl1zh hg0dv cq4sa ja2nb wh5vv ot4sh qe0jx yt6xs vc0qx nb1am rf2zl kn5hq xg5hk mz7yg aq3uw xh7pw sa7ok wt5ot io6hd pn1je lo6vx hq5cc wp6fc cs7fe yw2ka gy3sd nr0ry am3yt pl0rl ik0tn ub5tq sh0ja ee2it nh6qz xz1ma se0rx is7rn kc1xv cb6ft rx2mz wj7qf.
The leftmost word is xh. Its right neighbour is jz, so the first output word is jz.
Now, we need to find a word that starts with xh. The word is xh7pw. Its right neighbour is sa7ok, so the next output word is sa7ok.
Now, we need to find a word that starts with pw. The word is pw6hg. Its right neighbour is rk7cb, so the next output word is rk7cb.
Now, we need to find a word that starts with hg. The word is hg0dv. Its right neighbour is cq4sa, so the next output word is cq4sa.
Now, we need to find a word that starts with dv. The word is dv2sn. Its right neighbour is ew3rk, so the next output word is ew3rk.
Now, we need to find a word that starts with sn. The word is sn6iv. Its right neighbour is qh1va, so the next output word is qh1va.
Now, we need to find a word that starts with iv. The word is iv0vl. Its right neighbour is zs7qh, so the next output word is zs7qh.
Now, we need to find a word that starts with vl. The word is vl2kc. Its right neighbour is va5cq, so the next output word is va5cq.
Now, we need to find a word that starts with kc. The word is kc1xv. Its right neighbour is cb6ft, so the next output word is cb6ft.
Now, we need to find a word that starts with xv. The word is xv4vn. Its right neighbour is me3af, so the next output word is me3af.
Now, we need to find a word that starts with vn. The word is vn5zn. Its right neighbour is ok1ks, so the next output word is ok1ks.
Now, we need to find a word that starts with zn. The word is zn5qv. Its right neighbour is ks5ew, so the next output word is ks5ew.
Now, we need to find a word that starts with qv. The word is qv6gt. Its right neighbour is ft7me, so the next output word is ft7me.
Now, we need to find a word that starts with gt. The word is gt3bc. Its right neighbour is em3zs, so the next output word is em3zs.
Now, we need to find a word that starts with bc. The word is bc7qi. Its right neighbour is jz7em, so the next output word is jz7em.
There is no word that starts with qi, so we are done with the matching.
Therefore the answer is: jz sa7ok rk7cb cq4sa ew3rk qh1va zs7qh va5cq cb6ft me3af ok1ks ks5ew ft7me em3zs jz7em.
<FEW MORE EXAMPLES>
Your question: ap cb ch5ya gb6lt uu6le vn0pc og0ef md6ki jx0ph md4ki mq5ox vp1rx zp1xj is5am uq5fb te3rz eq3he cb0md he2zp fe2re ef6yp vn5pc ui3yt kb1ji qg2mq am4vp ez3eq lt5fi hw4eg lz2te wn5kd kb2ji le6wk vp3rx yt3lq rx6gb ey4dx ji3fe lq1dq lz0te wk7sl am6vp zi0up ki5kb ek7uu re0vq cs3ez vq5lz dx6se lt3fi xp2km fe3re bz7hw rx2gb yp6qg gb4lt at4cs fi7vn ox1nl fi5vn ph3zi rz4is kd2bz ji1fe nl3kk ki2kb yo6ey te1rz fd5at qb7ia bn2xp cb4md ya2wn gd7sq xj2jg rp6bl ap1bn is4am se5ui re5vq eg4uq cf6fj fb6jx ll4ic sl4ch qs3nf sp5fd qj6bf dq1og rz1is km6yo vq3lz up5sp wc5iv
Reason step by step. Clearly mark your answer by writing ’Answer: <your answer>’ as last line.

### D.2 PEN generation code

Figure: 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]$.

### D.3 PER Multi generation code

Figure: Figure 17: Code employed for generating instances of the Pointer Execution Reverse Multicount task and its associated subtasks. The hyperparameters employed include a length ranging between $[10,20]$.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: The following questions are about Theorem 1.
1. 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$.)

The following questions are about Theorem 2.
1. How's the definition of CoT different from just autoregressive decoding?

The following questions are about Theorem 4.
1. Lines 74 & 386: Isn't $\mathsf{L}$ a class of decision problems? Shouldn't one say $\mathsf{FL}$ instead of $\mathsf{L}$ here?
2. 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.
3. 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)$.
4. 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.
5. 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$.
6. 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.)

Here's my suggestion for how to actually formalize "SSMs only have _____ computational power" into a theorem statement to replace the current Theorem 4.

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

Now, 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 _____."

The 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.
soundness: 2
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.
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.
weaknesses: 1. The proof of Theorem 1 appears to rely on the specific format of the prompt (see Questions below).
2. 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).
3. 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.)

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: See the weakness. I am happy to raise my score if the authors can address the concerns proposed by reviewers.
soundness: 3
strengths: - Originality: This paper precisely defines the problem and proposes new theorems showing new results.
- Clarity and rigor: The theoretical and empirical sections are clearly structured, and concepts are clearly defined. 
- 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.
- 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.
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.
weaknesses: Note: Unfortunately I am not a domain expert in theoretical computer science, and my evaluations are based on educated guess.

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

References:  
[1] Polu, Stanislas, and Ilya Sutskever. "Generative language modeling for automated theorem proving." arXiv preprint arXiv:2009.03393 (2020).  
[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.  
[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).  
[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).

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 4
questions: Authors could also clarify the numerical experiments and their relationship to the main theorem with respect to layer number.
soundness: 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.
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.
weaknesses: No real weakness. Potentially authors could spend more time comparing their results to Peng for readers.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: Minor comments and suggestions:

There is a formatting error causing the heading of section 7 to come too close to the previous paragraph.

A summary figure of the empirical results could also be useful in the main manuscript if space limitations allow.

The “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.
soundness: 3
strengths: * Well written
* Well referenced
* Settles important questions about the limitations of current architectures of interest for sequence modeling.

This kind of theoretical work is very much needed.
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.
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.
* 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.

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

Computational 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?

Meta-review: This paper empirically and theoretically analyzes the computational limitations of Structured State Space Models (SSMs). The authors introduce three theorems: the inability of SSMs to compose functions, exponential scaling of compute when performing chain-of-thought, and an inability to solve NL-complete problems (unless L=NL). These theorems are backed up by empirical evidence in several different reasoning tasks.

Most reviewers agreed that the paper is original: it echos findings for transformers but applies them to the SSM architecture and yields new theoretical insights which are likely to be very valuable to the SSM community. These theoretical insights are further backed up by experiments demonstrating the limitations of function composition in SSMs. Overall, reviewers generally agreed that the paper was well-structured, with proofs being clear for each theorem.

As is common for theoretical papers of this kind, and as noted by several reviewers, it is not clear how large the potential gap is between the theoretical results presented here and practical applications. For example, in practice, methods such as search and self-correction are often used in combination with SSMs to handle complex problems, and as a result it may be possible to mitigate some of the challenges of SSMs by relying on these. However, the authors now note this directly in the revised manuscript, and reviewers agree that understanding the limitations of SSMs architecturally (without such additions) is still very valuable.

All reviewers agree that this paper is worth accepting for the reasons above, and I similarly recommend acceptance.

Decision: Accept (Poster)