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

Nikola Zubić1, Federico Soldá2,∗, Aurelio Sulser2,∗, Davide Scaramuzza1
1Robotics and Perception Group, University of Zurich, Switzerland
<EMAIL_ADDRESS><EMAIL_ADDRESS>
2Algorithms and Optimization Group, ETH Zurich, Switzerland
<EMAIL_ADDRESS><EMAIL_ADDRESS>
*Equal contribution

###### 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 [28, 10, 37] and computer vision [27, 47, 46]
to scientific computing [22, 14] and autonomous systems [15, 2]. 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 [3]. The mastery of function composition is essential
for this objective as mathematical problem solving [17], learning discrete
algorithms [35, 39], logical reasoning [20], and dynamic programming [6] are
all deeply compositional tasks. However, tasks requiring complex reasoning
over sequences, particularly those involving function composition [30] and
compositional tasks [6], 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 [38] like the GPT-4o
find it challenging to handle tasks needing deep compositionality [6]. 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 [24]. For this reason, the Structured
State Space Models (SSMs) [12, 11] 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 [9, 32], 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 [18] (SSM-Attention hybrid model) only achieves 17%
accuracy.

Existing research has experimentally confirmed the inability of Transformers
to perform function composition and compositional tasks [6, 45], 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 TC0 [24], just like SSMs
[23], emphasizing their limitations. The impossibility of function composition
for Transformers has been theoretically studied in [30]. 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) [40] steps (Theorems 1 and 2). 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.

##  3 Function Composition Requires Wide Models

The function composition problem has been introduced in [30] 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’_ [30], [13].

Next, we give a precise formulation of the _function composition problem_ due
to [30]. 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. 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. 2.

the second part consists of $|B|$ sentences describing the function $f$, e.g.
_’the birthday of Nicolas Chopin is April 15, 1771’_ ,

  3. 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 [30], [42]. 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 [30] 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, it follows that $q\leq R/(3n\log n)$. ∎

##  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 [40], 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 [25] 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 [29], 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, 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.

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

In [30], 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[30].

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 [30], 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 [23], it was established that linear and S6-
SSMs [11] 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 [23], 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 even to the
case of linear and S6- SSMs with $\log(n)$ CoT steps.

##  6 Experiments

To evaluate the inability of various sequence models in addressing function
composition tasks (Sec. 6.1a), 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.1b). Subsequently,
we proceed to compositional tasks involving multi-digit multiplication,
dynamic programming, and Einstein’s puzzle (Par. 6.1c). We investigate the
effects of CoT prompting (Sec. 6.2) and conduct a thorough error analysis to
understand the failure points and underlying reasons for this erroneous
behaviour (Sec. 6.3).

We conduct GPT experiments using the ChatGPT API [28], 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 [30, 6] 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 [21]. 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 [18] (joint Mamba and Attention) with 7B
parameters, Mamba [11] with 2.8B parameters, S4-H3 [12, 7] with 2.7B
parameters, GPT-4 [28], and GPT-4o models. Qualitative results are presented
in the Fig. 1. As illustrated in Fig. 1, all models failed to correctly answer
questions across the three composition axes.

Problem 1 - Spatial axis Question: Rectangle is to the west of the pentagon.
The triangle is to the north of the square. The rectangle is to the south of
the square. The triangle is to the west of the circle. Where is the square
located in relation to the pentagon? Jamba: East  ✗ Mamba: Northeast  ✗ GPT-4:
Northeast  ✗ GPT-4o: North  ✗ Correct: Northwest.  ✓

Problem 2 - Temporal axis Question: Anne is the younger sister of Erwin, Erwin
is the elder brother of Daniel. Is Anne younger than Daniel? Jamba: Yes  ✗
Mamba: Yes  ✗ GPT-4: Yes  ✗ GPT-4o: Yes  ✗ Correct: Not enough information.  ✓

Problem 3 - Relationship axis Question: Alan is the son of Marco, Joe is the
son of Alan. Does Alan have any grandchildren? Jamba: Yes  ✗ Mamba: Yes  ✗
GPT-4: No  ✗ GPT-4o: No  ✗ Correct: Not enough information.  ✓

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 [28], 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 [17], 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 [33] dataset features 250 Boolean expressions that
the model must evaluate. In Temporal-NLI [36] 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 [26] 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 [28] |  GPT-4 [28] |  Jamba [18] |  Mamba [11] |  S4-H3 [12, 7]
---|---|---|---|---|---
Math-QA [17] | $51.8\%$ | $51.0\%$ | $42.2\%$ | $35.0\%$ | $28.6\%$
BIG-Bench Hard [33] | $56.8\%$ | $58.4\%$ | $78.2\%$ | $67.0\%$ | $60.6\%$
Temporal-NLI [36] | $79.4\%$ | $77.2\%$ | $69.8\%$ | $59.2\%$ | $54.6\%$
SpaRTUN [26] | $80.8\%$ | $61.4\%$ | $50.8\%$ | $42.2\%$ | $35.2\%$

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 [28] |  GPT-4 [28] |  Jamba [18] |  Mamba [11] |  S4-H3 [12, 7]
---|---|---|---|---|---
Algebra | $51\%$ | $47\%$ | $42\%$ | $36\%$ | $29\%$
Calculus | $50\%$ | $48\%$ | $41\%$ | $34\%$ | $28\%$
Combinatorics | $88\%$ | $70\%$ | $48\%$ | $38\%$ | $33\%$
Game theory | $30\%$ | $40\%$ | $50\%$ | $41\%$ | $32\%$
Trigonometry | $40\%$ | $50\%$ | $30\%$ | $26\%$ | $21\%$

Table 2: Performance of models on various topics within the Math-QA [17]
dataset. Input dependency consistently improves performance, with Mamba [11]
consistently outperforming S4-H3 [12, 7].

The results presented in Tables 2 and 2 highlight several key observations
regarding the performance of various models across different composition
tasks. Notably, Mamba [11] consistently outperforms the S4-H3 [12, 7] 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
[33] 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, 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).

Figure 2: Jamba [18] performance on multiplication, DP and puzzle tasks. For
DP various models are shown. All struggle with compositional tasks, especially
for larger input size.

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 [16]:
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 [6], with input list containing from 2 to 6 elements. Prompting details are
shown in the A-B.3.

Einstein’s puzzle is a well-known logic puzzle commonly used as a benchmark
for solving constraint satisfaction problems [31]. 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.

###  6.2 CoT experiments

Next, we evaluate how the popular chain-of-thought (CoT) prompting method [40]
affects the performance of GPT-4o [28], Jamba [18], Mamba [11] and S4-H3 [12]
models on compositional tasks from Sec. 6.1. 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.

###  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 [7, 11, 26].

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

Algorithm 1 Multiply two numbers

1:function multiply($x[1..p]$, $y[1..q]$) $\triangleright$ multiply $x$ for
each $y[i]$

2: for $i=q$ to $1$ do

3: carry = $0$

4: for $j=p$ to $1$ do

5: $t=x[j]\times y[i]$

6: $t\mathrel{+}=\text{carry}$ $\triangleright$ add carry

7: carry $=t\div 10$

8: digits $[j]=t\mod 10$

9: end for

10: summands[$i$] = digits

11: end for

12: product $=\sum_{i=1}^{q}\text{summands}[q+1-i]\cdot 10^{i-1}$

13: return product

14:end function

Figure 3: Example of 2-by-1 digit multiplication (87 $\times$ 9). Operations
on graph include: inputs, multiply 1-digit, carry, sum, mod 10 and output.

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). Corresponding algorithm is on
the left of the Fig. 3 \- Alg. 1.

#### Error propagation

We investigate the types of errors encountered by SSMs. Specifically, Fig. 5
illustrates the errors produced by the S4-H3 model [12, 7]. 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, 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 [6] 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 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.

Figure 5: SSMs and Transformers learn shortcuts that seem to 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 even when the overall response
is incorrect. For example, using Mamba [11] 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 [6], we find that SSMs learn shortcuts, performing fewer
operations (illustrated by the red and green subgraphs in Fig. 5). 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
[8, 19, 34, 5]. 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 [41].

###  6.4 Learning Algorithmic Compositions

Finally, we conduct a comprehensive analysis of the capabilities of SSM-based
models, along with GPT-4o [28], 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 [40].
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.

##  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 [30, 6]. These tasks are crucial in applications like
mathematical problem-solving [17], algorithm learning [35], logical reasoning
[20], and dynamic programming [6]. Transformers, despite their capabilities,
have been shown to struggle with function composition, which is essential for
understanding relational information in data [13]. Research has highlighted
the architectural and training limitations that prevent these models from
maintaining accuracy over multiple reasoning steps, leading to issues like
hallucinations [24]. Studies by [23] and [30] have identified that both
Transformers and SSMs belong to weak complexity classes, such as logspace-
uniform TC0, 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 [40]. 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 [25].

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

## References

  * [1] 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 over task complexity, 2023.
  * [2] Konstantinos Bousmalis, Giulia Vezzani, Dushyant Rao, Coline Manon Devin, Alex X. Lee, Maria Bauza Villalonga, Todor Davchev, 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 Abdolmaleki, Oliver Groth, Jean-Baptiste 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.
  * [3] 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.
  * [4] Leonardo de Moura and Nikolaj Bjørner.  Z3: An efficient smt solver.  In C. R. Ramakrishnan and Jakob Rehof, editors, Tools and Algorithms for the Construction and Analysis of Systems, 2008.
  * [5] Mengnan Du, Fengxiang He, Na Zou, Dacheng Tao, and Xia Hu.  Shortcut learning of large language models in natural language understanding.  Commun. ACM, 2022.
  * [6] Nouha Dziri, Ximing Lu, Melanie Sclar, 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 on compositionality.  In NeurIPS, 2023.
  * [7] 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.
  * [8] Robert Geirhos, Jörn-Henrik Jacobsen, Claudio Michaelis, Richard S. Zemel, Wieland Brendel, Matthias Bethge, and Felix Wichmann.  Shortcut learning in deep neural networks.  Nature Mach. Intell., 2020.
  * [9] Karan Goel, Albert Gu, Chris Donahue, and Christopher Ré.  It’s raw! audio generation with state-space models.  Int. Conf. Mach. Learn., 2022.
  * [10] Gemini Team Google.  Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context.  ArXiv, abs/2403.05530, 2024.
  * [11] Albert Gu and Tri Dao.  Mamba: Linear-time sequence modeling with selective state spaces, 2023.
  * [12] Albert Gu, Karan Goel, and Christopher Ré.  Efficiently modeling long sequences with structured state spaces.  In ICLR, 2022.
  * [13] Xinyan Guan, Yanjiang Liu, Hongyu Lin, Yaojie Lu, Ben He, Xianpei Han, and Le Sun.  Mitigating large language model hallucinations via autonomous knowledge graph-based retrofitting.  In AAAI, 2024.
  * [14] Derek Hansen, Danielle Maddix Robinson, Shima Alizadeh, Gaurav Gupta, and Michael Mahoney.  Learning physical models that can respect conservation laws.  In Int. Conf. Mach. Learn., 2023.
  * [15] Elia Kaufmann, Leonard Bauersfeld, Antonio Loquercio, Matthias Müller, Vladlen Koltun, and Davide Scaramuzza.  Champion-level drone racing using deep reinforcement learning.  Nature, 2023.
  * [16] Jon Kleinberg and Eva Tardos.  Algorithm Design.  Addison-Wesley Longman Publishing Co., Inc., USA, 2005.
  * [17] 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 NeurIPS, 2023.
  * [18] 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: A hybrid transformer-mamba language model, 2024.
  * [19] Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang.  Transformers learn shortcuts to automata.  ICLR, 2023.
  * [20] 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, 2023.
  * [21] Pan Lu, Baolin Peng, Hao Cheng, Michel Galley, Kai-Wei Chang, Ying Nian Wu, Song-Chun Zhu, and Jianfeng Gao.  Chameleon: Plug-and-play compositional reasoning with large language models.  In NeurIPS, 2023.
  * [22] Amil Merchant, Simon Batzner, Samuel S. Schoenholz, Muratahan Aykol, Gowoon Cheon, and Ekin Dogus Cubuk.  Scaling deep learning for materials discovery.  Nature, 2023.
  * [23] William Merrill, Jackson Petty, and Ashish Sabharwal.  The illusion of state in state-space models, 2024.
  * [24] William Merrill and Ashish Sabharwal.  The parallelism tradeoff: Limitations of log-precision transformers.  Trans. Assoc. Comput. Linguist., 2023.
  * [25] William Merrill and Ashish Sabharwal.  The expressive power of transformers with chain of thought, 2024.
  * [26] Roshanak Mirzaee and Parisa Kordjamshidi.  Transfer learning with synthetic corpora for spatial role labeling and reasoning.  In Proc. Conf. Empirical Methods in Nat. Lang. Process. Association for Computational Linguistics, 2022.
  * [27] Eric Nguyen, Karan Goel, Albert Gu, Gordon Downs, Preey Shah, Tri Dao, Stephen Baccus, and Christopher Ré.  S4nd: Modeling images and videos as multidimensional signals with state spaces.  In NeurIPS, 2022.
  * [28] OpenAI.  Gpt-4 technical report, 2023.
  * [29] Christos H. Papadimitriou and Michael Sipser.  Communication complexity.  In Proc. Annu. ACM Symp. Theory Comput. Association for Computing Machinery, 1982.
  * [30] Binghui Peng, Srini Narayanan, and Christos Papadimitriou.  On limitations of the transformer architecture, 2024.
  * [31] Patrick Prosser.  Hybrid algorithms for the constraint satisfaction problem.  Comput. Intell., 9, 1993.
  * [32] Yair Schiff, Chia-Hsiang Kao, Aaron Gokaslan, Tri Dao, Albert Gu, and Volodymyr Kuleshov.  Caduceus: Bi-directional equivariant long-range dna sequence modeling, 2024.
  * [33] 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-thought can solve them.  arXiv preprint arXiv:2210.09261, 2022.
  * [34] 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.
  * [35] Jonathan Thomm, Aleksandar Terzic, Geethan Karunaratne, Giacomo Camposampiero, Bernhard Schölkopf, and Abbas Rahimi.  Limits of transformer language models on learning algorithmic compositions, 2024.
  * [36] Shivin Thukral, Kunal Kukreja, and Christian Kavouras.  Probing language models for understanding of temporal expressions.  In BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP, 2021.
  * [37] 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.
  * [38] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  NeurIPS, 2017.
  * [39] Petar Veličković and Charles Blundell.  Neural algorithmic reasoning.  Patterns, 2021.
  * [40] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou.  Chain-of-thought prompting elicits reasoning in large language models.  In NeurIPS, 2022.
  * [41] Sohee Yang, Elena Gribovskaya, Nora Kassner, Mor Geva, and Sebastian Riedel.  Do large language models latently perform multi-hop reasoning?  ArXiv, 2024.
  * [42] Andrew Chi-Chih Yao.  Some complexity questions related to distributive computing(preliminary report).  In Proc. Annu. ACM Symp. Theory Comput. Association for Computing Machinery, 1979.
  * [43] Amir Yehudayoff.  Pointer chasing via triangular discrimination.  Comb. Probab. Comput., 2020.
  * [44] Chiyuan Zhang, Maithra Raghu, Jon Kleinberg, and Samy Bengio.  Pointer value retrieval: A new benchmark for understanding the limits of neural network generalization, 2022.
  * [45] 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.
  * [46] 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.
  * [47] Nikola Zubić, Mathias Gehrig, and Davide Scaramuzza.  State space models for event cameras.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2024.

[sections] [sections]l1

##  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 [30]. 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 we get that
$2Rdp\geq n/(2000k)-2k\log n$ which gives $R\geq\frac{3}{100}\frac{\sqrt{n\log
n}}{dp}$ ∎

##  Appendix B Compositional Tasks Details

###  B.1 Multiplication

We show examples of few-shot and CoT prompting methods for multiplication task
(Figs. 6 & 7).

⬇

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. Repeat this process for each digit of the
multiplicand, and then add up all the partial products to obtain the final
result. Here are examples:

\parQuestion: what’s 32 times 8? Answer 256.

Question: what’s 69 times 3? Answer 207.

Question: what’s 93 times 6? Answer 558.

\parQuestion: what’s 76 times 8? Answer:

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

⬇

|\textbf{Question:}| What is 904 times 74?

\par\par|\textbf{Scratchpad:}| Let’s perform the multiplication step by step:

\parLet’s multiply 904 by the digit in the ones place of 74, which is 4.

\par1. Multiply 4 by the digit in the ones place of 904, which is 4. This
gives 4 x 4 = 16. Write down the result 6 and carry over the 1 to the next
step.

2. Multiply 4 by the digit in the tens place of 904, which is 0. Add the carryover from the previous step to account for this. This gives (0 x 4) + 1 = 1. Write down the result 1.

3. Multiply 4 by the digit in the hundreds place of 904, which is 9. This gives 9 x 4 = 36. Write down the result 36.

4. The partial product for this step is A=3616 which is the concatenation of the digits we found in each step.

\parNow, let’s multiply 904 by the digit in the tens place of 74, which is 7.

\par5. Multiply 7 by the digit in the ones place of 904, which is 4. This
gives 4 x 7 = 28. Write down the result 8 and carry over the 2 to the next
step.

6. Multiply 7 by the digit in the tens place of 904, which is 0. Add the carryover from the previous step to account for this. This gives (0 x 7) + 2 = 2. Write down the result 2.

7. Multiply 7 by the digit in the hundreds place of 904, which is 9. This gives 9 x 7 = 63. Write down the result 63.

8. The partial product for this step is B=6328 which is the concatenation of the digits we found in each step.

\parNow, let’s sum the 2 partial products A and B, and take into account the
position of each digit: A=3616 (from multiplication by 4) and B=6328 (from
multiplication by 7 but shifted one place to the left, so it becomes 63280).
The final answer is 3616 x 1 + 6328 x 10 = 3616 + 63280 = 66896.

Figure 7: A sample scratchpad for the multiplication task.

###  B.2 Einstein’s Puzzle

#### Data Construction

Following [6], 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 [4] 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 shows an example of a scratchpad.

⬇

This is a logic puzzle. There are 3 houses (numbered 1 on the left, 3 on the
right). Each has a different person in them. They have different
characteristics:

- Each person has a unique name: peter, eric, arnold

- People have different favorite sports: soccer, tennis, basketball

- People own different car models: tesla model 3, ford f150, toyota camry

\par1. The person who owns a Ford F-150 is the person who loves tennis.

2. Arnold is in the third house.

3. The person who owns a Toyota Camry is directly left of the person who owns a Ford F-150.

4. Eric is the person who owns a Toyota Camry.

5. The person who loves basketball is Eric.

6. The person who loves tennis and the person who loves soccer are next to each other.

\parLet’s think step by step. Please first briefly talk about your reasoning
and show your final solution by filling the blanks in the below table.

\par$ House: ___ $ Name: ___ $ Sports: ___ $ Car: ___

$ House: ___ $ Name: ___ $ Sports: ___ $ Car: ___

$ House: ___ $ Name: ___ $ Sports: ___ $ Car: ___

\parReasoning:

Step 1: First apply clue <Arnold is in the third house.> We know that The Name
in house 3 is arnold.

Step 2: Then combine clues: <The person who loves tennis and the person who
loves soccer are next to each other.> <The person who loves basketball is
Eric.> Unique Values Rules and the fixed table structure. We know that The
Name in house 1 is eric. The FavoriteSport in house 1 is basketball. The Name
in house 2 is peter.

Step 3: Then apply clue <Eric is the person who owns a Toyota Camry.> We know
that The CarModel in house 1 is toyota camry.

Step 4: Then apply clue <The person who owns a Toyota Camry is directly left
of the person who owns a Ford F-150.> and Unique Values We know that The
CarModel in house 2 is ford f150. The CarModel in house 3 is tesla model 3.

Step 5: Then apply clue <The person who owns a 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 3 is soccer.

The puzzle is solved.

\parFinal solution:

$ House: 1 $ Name: Eric $ Sports: Basketball $ Car: Camry

$ House: 2 $ Name: Peter $ Sports: Tennis $ Car: Ford

$ House: 3 $ Name: Arnold $ Sports: Soccer $ Car: Tesla

\par

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 & 10), following [6].

⬇

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.

\parOutput a list with "1" for chosen numbers and "2" for unchosen ones. If
multiple solutions exist, select the lexicographically smallest. input = [3,
2, 1, 5, 2].

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

⬇

Question: Let’s solve input = [3, 2, 1, 5, 2].

\par\parScratchpad: dp[4] = max(input[4], 0) = max(2, 0) = 2

dp[3] = max(input[3], input[4], 0) = max(5, 2, 0) = 5

dp[2] = max(dp[3], input[2] + dp[4], 0) = max(5, 1 + 2, 0) = 5

dp[1] = max(dp[2], input[1] + dp[3], 0) = max(5, 2 + 5, 0) = 7

dp[0] = max(dp[1], input[0] + dp[2], 0) = max(7, 3 + 5, 0) = 8

\parFinally, we reconstruct the lexicographically smallest subsequence that
fulfills the task objective by selecting numbers as follows. We store the
result on a list named "output".

\parLet can_use_next_item = True.

Since dp[0] == input[0] + dp[2] (8 == 3 + 5) and can_use_next_item == True, we
store output[0] = 1. We update can_use_next_item = False.

Since dp[1] != input[1] + dp[3] (7 != 2 + 5) or can_use_next_item == False, we
store output[1] = 2. We update can_use_next_item = True.

Since dp[2] != input[2] + dp[4] (5 != 1 + 2) or can_use_next_item == False, we
store output[2] = 2. We update can_use_next_item = True.

Since dp[3] == input[3] (5 == 5) and can_use_next_item == True, we store
output[3] = 1. We update can_use_next_item = False.

Since dp[4] != input[4] (2 != 2) or can_use_next_item == False, we store
output[4] = 2.

\parReconstructing all together, output=[1, 2, 2, 1, 2].

\par

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 [18] on multiplication and puzzle tasks, and
various models on DP task after using CoT.

Figure 11: Jamba’s [18] 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.

The leftmost heatmap on Fig. 11 represents the Jamba [18] 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 [28], Jamba [18], Mamba [11], and S4-H3 [12, 7]—on dynamic
programming tasks with CoT prompting [40]. GPT-4o [28] 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 [40] 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 & 13.
GPT-4o [28] is always the best model, followed by Jamba [18], then Mamba [11],
then S4-H3 [7, 12]. While CoT helps, it is not enough to solve the task.

Figure 12: Comparison of different models on multiplication task using CoT.

Figure 13: Comparison of different models on puzzle task using CoT.

###  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 shows
the results, and consistently CoT outperforms Few-shot prompting, and Few-shot
prompting outperforms Zero-shot prompting.

Figure 14: Comparison of different models on multiplication task using few-
shot prompting.

##  Appendix D Algorithmic Compositions

Following [35], 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 [1] and rooted in the Pointer Value Retrieval
framework [44], 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 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 [40]. Remarkably, none of the models,
including the state-of-the-art GPT-4o [28], succeeded in solving the PEN task
[35]. 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).

Table 3: Model Accuracy for PEN task

Model | Prompt Setting | Accuracy [%]
---|---|---
GPT-4o [28] | Zero-shot | 0.00
Few-shot | 0.00
CoT | 0.00
Jamba | Zero-shot | 0.00
Few-shot | 0.00
CoT | 0.00
Mumba | Zero-shot | 0.00
Few-shot | 0.00
CoT | 0.00
S4-H3 [12, 7] | Zero-shot | 0.00
Few-shot | 0.00
CoT | 0.00

Table 4: Model Accuracy for PER Multi task

Model | Prompt Setting | Accuracy [%]
---|---|---
GPT-4o [28] | Zero-shot | 0.00
Few-shot | 0.01
CoT | 0.09
Jamba | Zero-shot | 0.00
Few-shot | 0.00
CoT | 0.00
Mumba | Zero-shot | 0.00
Few-shot | 0.00
CoT | 0.00
S4-H3 [12, 7] | Zero-shot | 0.00
Few-shot | 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 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

⬇

Example: eg jy vm3zc si2zf nn4ll zf5ka ki7xd ew0si xp3og il5js xn6yx my7ec
xu2gb if2my fy3so ec2il ob5ch kt5if zc4xp ka3mj og1ud zf2ka yh3ux hx2kt vc2pf
jy4qd lj1xu wy5hx bd4xa my4ec at1kb jy3qd ux1fl ew3si ds2qz qd7ew xa1ay si1zf
ch4lj js3rf fl6xn mj7wy zy6rq zh2gu bj3rb if0my pg5ds yv3hs zu3ob ta7qi ji2bj
mj1wy rq7ul mn3fw ay4qu kt2if kr3qb pr0ah tg0at uc1vx xd1pd wy4hx dr6fy mk0vj
sm0pg jl2mo rb1bd il2js vn6kr km4aq eg7nn ka6mj qu4vc hx7kt ll2lb ec6il ud2vn
di3xs pd6ji qd6ew yx7zu rh4qn lb1ki js5rf iv3yh jj0fa kb3sm lh6yk so0iv bx6rs
qz1vm mw7bm gb2xo uy0ms qb2zy zm0pz xo4tg zx5jm

\parAnswer: jy ka6mj zf5ka ec6il js5rf ew0si wy4hx qd6ew mj1wy if0my il2js
my4ec si1zf kt2if hx7kt jy4qd

\par<FEW MORE EXAMPLES>

\parYour question: ey wt kj5yo jz0aa nu4yw gp2ro mv6kj nk2qz tr3mp ro7rk tu5xj
rk0sj ad2lx up3vd ta7rv qz6ob rc7nt aa4nk mb6mm ob7us jw5wb wt4jz nn4sr wt0jz
ev0fa gp1ro sr1nu sj0ku xs0ta us5up mp6jw vd1gp xj3cs sj7ku ol3vv vd3gp wd2mv
wr4cz dg0py ro5rk jt6ev bv0cf yb2qv ch2ss xa3be nb5id lx4jt dz5ht wb5wd fb3ax
fa0tu jn5ps rv7qj qa7el rn7ad lz3fk mm1tr yd3lv nt0xs lh4zk mr3ou ja5sn gi5ub
rk4sj wm7zm jz3aa be4mb kw3bh qj4xa cg0mi jl2rn kv1wg qt5mr ye3kg yr5ol nk7qz
ub1dg ob3us cs7so gw4vk ey4wm qz2ob qv4jl xz4hc li0yb oy4qu zm2yr up7vd ou7li
rx4wc yw7gi aa2nk yo3qt yz5cx vv6nn us7up

\parClearly mark your answer by writing ’Answer: <your answer>’ as 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-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

⬇

import itertools

import numpy as np

letter_chars = list("abcdefghijklmnopqrstuvwxyz")

big_letter_chars = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")

number_chars = list("0123456789")

class DataConfig:

def __init__(self, min_len, max_len, min_hops, max_hops, learn_mode,
ambiguous, no_green_confusion):

self.min_len = min_len

self.max_len = max_len

self.min_hops = min_hops

self.max_hops = max_hops

self.learn_mode = learn_mode

self.ambiguous = ambiguous

self.no_green_confusion = no_green_confusion

def get(self, key, default):

return getattr(self, key, default)

class PointerExecutionNeighbour:

def __init__(self, data_cfg):

self.length_low = data_cfg.min_len

self.length_high = data_cfg.max_len + 1

self.hops_low = data_cfg.min_hops

self.hops_higher = data_cfg.max_hops + 1

self.all_2tuples = ["".join(t) for t in itertools.product(letter_chars,
repeat=2)]

self.learn_mode = data_cfg.get("learn_mode", "next")

self.data_choices = list(number_chars[:8])

self.ambiguous = data_cfg.get("ambiguous", False)

self.no_green_confusion = data_cfg.get("no_green_confusion", False)

def generate_double_pointer_execution(self, n_samples):

lengths = np.arange(self.length_low, self.length_high)

samples = []

answers = []

while len(samples) < n_samples:

length = np.random.choice(lengths)

n_matching_hops = np.random.choice(np.arange(self.hops_low,
min(self.hops_higher, length // 2)))

tuple_choices = np.random.choice(self.all_2tuples, length * 7, replace=False)

# select the positions where the green matching sequence will be

positions = np.random.choice(np.arange(1, length), size=n_matching_hops,
replace=False)

cnt = 0

question_words1 = ["" for _ in range(length)]

question_words2 = ["" for _ in range(length)]

remaining_positions = np.random.permutation([i for i in range(1, length) if i
not in positions])

question_words1[0] = tuple_choices[cnt]

answer_learnseq = [question_words1[0]]

for pos in positions:

question_words1[pos] = (tuple_choices[cnt] +
np.random.choice(self.data_choices) + tuple_choices[cnt + 1])

answer_learnseq.append(question_words1[pos])

cnt += 1

cnt += 1

cnt_confuse = cnt + length

positions_next = np.random.permutation(positions)

question_words2[0] = tuple_choices[cnt]

answer = [question_words2[0]]

# select the positions where the doppelgangers of the neighbours will be

positions_confuse = np.setdiff1d(np.arange(1, length), positions_next)[0 :
len(positions_next)]

np.random.shuffle(positions_confuse)

for i, pos in enumerate(positions_next):

two_big_letters = np.random.choice(self.data_choices, size=2,
replace=self.ambiguous)

question_words2[pos] = (tuple_choices[cnt] + two_big_letters[0] +
tuple_choices[cnt + 1])

question_words2[positions_confuse[i]] = (tuple_choices[cnt] +
two_big_letters[1] + tuple_choices[cnt + 1])

answer.append(question_words2[pos])

cnt += 1

cnt_confuse += 1

cnt = max(cnt, cnt_confuse) + 1

remaining_next_positions = np.random.permutation([i for i in range(1, length)
if i not in positions_next and i not in positions_confuse])

for pos in remaining_positions:

question_words1[pos] = (tuple_choices[cnt] +
np.random.choice(self.data_choices) + tuple_choices[cnt + 1])

cnt += 1

if self.no_green_confusion:

cnt += 1

cnt += 1

for pos in remaining_next_positions:

question_words2[pos] = (tuple_choices[cnt] +
np.random.choice(self.data_choices) + tuple_choices[cnt + 1])

cnt += 2

answer_learnnext = [question_words2[0]]

for pos in positions:

answer_learnnext.append(question_words2[pos])

answer_seqnext = []

for i in range(len(answer_learnseq)):

answer_seqnext.append(answer_learnseq[i])

answer_seqnext.append(answer_learnnext[i])

answer.reverse()

question_words = []

for i in range(length):

question_words.append(question_words1[i])

question_words.append(question_words2[i])

question_str = (f"pe {self.learn_mode}: " + " ".join(["".join(x) for x in
question_words]) + " answer: ")

samples.append(question_str)

if self.learn_mode == "seq":

answers.append(" ".join(answer_learnseq))

elif self.learn_mode == "seqnext":

answers.append(" ".join(answer_seqnext))

elif self.learn_mode == "next":

answers.append(" ".join(answer_learnnext))

return samples, answers

def generate(self, n_samples):

samples, answers = self.generate_double_pointer_execution(n_samples)

return 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]$.

###  D.3 PER Multi generation code

⬇

import itertools

import numpy as np

letter_chars = list("abcdefghijklmnopqrstuvwxyz")

class DataConfig:

def __init__(self, min_len, max_len, logname, learn_mode="seq"):

self.min_len = min_len

self.max_len = max_len

self.logname = logname

self.learn_mode = learn_mode

def get(self, key, default):

return getattr(self, key, default)

class PointerExecutionReverseMulticount:

def __init__(self, data_cfg):

self.length_low = data_cfg.min_len

self.length_higher = data_cfg.max_len + 1

self.logname = data_cfg.logname

self.all_2tuples = ["".join(t) for t in itertools.product(letter_chars,
repeat=2)]

self.learn_mode = data_cfg.get("learn_mode", "seq")

assert self.learn_mode in ["seq", "multiseq", "seqrev", "multiseqrev"]

def generate_samples(self, n_samples):

lengths = np.arange(self.length_low, self.length_higher)

samples = []

answers = []

for _ in range(n_samples):

length = np.random.choice(lengths)

tuple_choices = np.random.choice(self.all_2tuples, length + 3, replace=False)

last_word = tuple_choices[-3] + tuple_choices[-2]

shuffled_tuple_choices1 = np.random.permutation(tuple_choices[:-3])

shuffled_tuple_choices2 = np.random.permutation(tuple_choices[:-3])

words = [ch1 + ch2 for ch1, ch2 in zip(shuffled_tuple_choices1,
shuffled_tuple_choices2)]

start = np.random.choice(words)

words.append(last_word)

if "rev" not in self.learn_mode:

answer = self.solve_seqnext(words, start, self.learn_mode)

else:

# change the 2tuple of the start of the start word to a random one

idx = words.index(start)

words[idx] = tuple_choices[-1] + words[idx][2:]

start = words[idx]

answer, answer_n_left = self.solve_seqnext(words, start, self.learn_mode)

if self.learn_mode == "seqrev":

answer = reversed([f"{w}" for i, w in enumerate(answer)])

if self.learn_mode == "multiseqrev":

answer = reversed([f"{w}.{i*n}" for i, (w, n) in enumerate(zip(answer,
answer_n_left))])

question = (f"prand {self.learn_mode}: " + " ".join(words) + " | " + start + " answer: ")

samples.append(question)

answers.append(" ".join(answer))

return samples, answers

def solve_seqnext(self, words, start, mode):

answer_next = []

matching_seq = []

current_word = start

idx = words.index(current_word)

n_left = 0

answer_n_left = []

while True:

matching_seq.append(current_word)

answer_next.append(words[idx + 1])

answer_n_left.append(n_left)

next_word = [(w, i) for i, w in enumerate(words) if
w.startswith(current_word[-2:])]

if len(next_word) == 0 and "rev" in mode:

break

assert len(next_word) == 1

current_word, new_idx = next_word[0]

if new_idx < idx:

n_left += 1

idx = new_idx

if current_word in matching_seq:

break

if "rev" in mode:

return matching_seq, answer_n_left

if "multi" in mode:

answer = []

for i, (w, n) in enumerate(zip(matching_seq, answer_n_left)):

answer.append(f"{w}.{i*n}")

return answer

return matching_seq

def generate(self, n_samples):

samples, answers = self.generate_samples(n_samples)

return samples, answers

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