Separations in the Representational Capabilities of Transformers and Recurrent Architectures

Thank you for your thoughtful comments and time.

Responses to the individual comments below.

“The experimental part is fairly brief. The analysis of computational or statistical learning complexity is left to future work.”

We respectfully disagree with this assessment. The central claims of the paper are theoretical in nature and we believe the empirical results are sufficiently extensive to support them and provide some context for the theoretical results.

Our work does include experiments for all primary tasks considered in the paper – apart from those related to associative recall, where extensive empirical evidence has already been provided in earlier works (see citations in the paper). Additionally, we consider five different recurrent architectures spanning traditional architectures such as LSTMs to more recently proposed ones such as Mamba, DSS, etc. Given the kind of statements made in the theoretical results, it seems natural to explore with experiments whether differences of a similar nature are exhibited in practice. We believe we have studied that fairly extensively. While it is true that experiments analyzing the statistical learning complexity of models are not present, we believe that it is far and somewhat detached from the central claims of the paper.

“Do you have any guess of which Boolean functions are conjectured to be hard to compute for 2-layers Tranformers of poly-logarithmic size?”

We do not have any strong conjectures at the moment, but there are a couple of directions worth thinking about.

• In our paper, we show that 2-layer Transformers with poly-log size can represent k-DNFs/k-CNFs with at most N terms. We suspect that for k-DNFs/k-CNFs with cubic ($\Omega(N^3)$) or more terms may be difficult for two-layer Transformers to represent with poly-log size.
• Due to circuit complexity bounds, functions outside of the complexity class TC0 are impossible for transformers even of polynomial size, and thus in particular for 2-layer transformers of poly-logarithmic size. This is likely to include foundational problems such as the evaluation of Boolean formulas. However, it is unclear if such tasks can represented by small-sized RNNs/SSMs.

“It seems your separation results are worst-case over the input space. Can you argue whether all/some separations still hold for typical inputs, if for instance a uniform distribution over the input space is assumed?”

Thanks for raising this question. We have some thoughts on this. Currently, most of the results in our paper are of a deterministic nature in the sense that a model is said to express a function $f$ if it can produce the same output as $f$ for all inputs in the domain of $f$. This is more typical when analyzing expressivity in the context of classification, i.e., $f: X \rightarrow \{0, 1\}$.

Upon some thinking over the past week, we believe that some of our lower bounds can indeed be extended to the average case on certain distributions, such as the uniform one. For instance, there is a well-studied Boolean function called Inner-product mod 2 (IP2 in short), for which we can show that any RNN or 1-layer Transformer must have linear size to achieve low error with respect to the uniform distribution. The proof follows from the arguments in Section C.2 in Vardi et. al [1]. We think that some of the lower bounds in our paper, such as Index Lookup and nearest neighbor/MQAR, can be extended to various distributions based on reductions from the IP2 problem. We will verify the proofs and include them in the next version of our paper.

[1] Vardi et. al. Size and Depth Separation in Approximating Benign Functions with Neural Networks. COLT 2021.

Thank you for your thoughtful comments and time.

“The analysis is specific to synthetic tasks with 1-layer recurrent models and Transformers …”

“How do we extend these results to deeper networks?”

We wish to clarify what may be a misunderstanding here – we should have been more explicit about this when we defined recurrent models on pg. 3. While our lower bounds for Transformers apply only to 1-layer models, our results for recurrent models apply to any depth. The way we have defined RNNs (Section 2), the transition function is allowed to be an arbitrary function which is very general and includes multi-layer versions of all architectures used in practice. When we state that an RNN needs a hidden state of size $\Omega(N)$ to solve a task, what we mean is that for any RNN with L layers, the sum of the size of hidden states of all layers has to be $\Omega(N)$ and thus the size of the model is $\Omega(N)$. Hence, our results show some tasks that can be solved with 1 or 2-layer Transformers (e.g. Index Lookup, Equality, Nearest Neighbour, etc) with poly-log size whereas any multi-layer RNN must have at least linear size (exponentially larger) to solve them. We will emphasize this point more clearly in Section 2 to avoid this confusion.

We agree with the reviewer that understanding the limitations of multi-layer Transformers (TF) is very important. However, proving lower bounds even for 1-layer TF has been challenging—there have been some very recent results [4] and most questions about (multi-layer) TF with sub-linear width remain open. Our lower bound results for 1-layer TF are more general and more interestingly apply to tasks solvable by small-sized RNNs or small-sized 2-layer TF, thus showing a clear separation. Existing lower bounds for multi-layer TF are not solely information-theoretic and rely on unproven conjectures, e.g. from circuit complexity. The situation mirrors somewhat that in computational complexity, where proving circuit lower bounds even for depth 2 or 3 has proved challenging for decades (https://shorturl.at/6lwUh).

Even for 1-layer Transformers (TF) we believe there are many interesting unanswered questions, some of which are answered in our work. (Q1) Are there tasks that cannot be solved by small 1-layer TFs but are solvable by much smaller 2-layer TF? (Q2) Since 1-layer TFs can solve tasks like Index lookup with poly-log size, while any multi-layer RNN needs linear size, are there tasks that small RNNs can solve but not 1-layer TFs?

(1) We show an exponential depth separation for tasks like Equality, Dyck, and Disjointness, where 1-layer TFs need linear width but 2-layer TFs solve them with log width. Such depth separation questions are widely studied for feedforward networks (see [1, 2, 3]). As far as we know, our results are the first to show exponential depth separation between 1-layer and 2-layer TFs on multiple tasks.

(2) Since 1-layer TFs of poly-log size can express tasks that multi-layer RNNs with sublinear size cannot, the lower bound on Dyck shows a task solvable by constant-sized RNNs but not by 1-layer TFs.

Regarding upper bounds or constructions for 1 or 2-layer TF, we see it as a strength rather than a limitation. We show multiple tasks that 1 or 2-layer TF can represent, whereas any multi-layer RNNs must be much larger regardless of depth.

[1] The Power of Depth for Feedforward Neural Networks.
[2] Depth Separation for Neural Networks.
[3] Representation benefits of deep feedforward networks.
[4] Representational strengths and limitations of transformers.

“With the goal of differentiating .. why these particular tasks were chosen and what makes them important … for language modelling.”

“Is there a way to motivate the selection of the tasks in this work?”

We discussed the task choices in the Introduction and further for Dycks in Section F. Briefly, our goal was to focus on tasks that appear natural or have strong justification in ML or linguistics research. For instance, in the MQAR task introduced in [1], they observed a perplexity gap in natural language modeling between Transformers (TF) and non-TF LMs, finding that non-TF language models struggled with texts that precisely mimic the MQAR task. Similarly, for the general version, i.e., the nearest neighbor task, multiple works [2, 3] found TF-based LLMs can mimic such behavior in practice. Dyck languages have been extensively studied in formal language theory and ML research. Tasks like String Equality and Index Lookup are natural tasks that are likely to be relevant as primitives in search and learning tasks. For example, in code execution, given arr = [6, 2, 8, 2, …, 3] followed by print(arr[i]), the task is essentially Index Lookup. Models might also perform such lookups when provided with line numbers for debugging.

[1] arxiv.org/abs/2312.04927
[2] arxiv.org/abs/2310.03016
[3] arxiv.org/abs/2404.11018

“The analysis is specific to synthetic tasks…”

“Are the results relevant for other task or other domains and is the relevance of these results very narrow?”

In the main paper, we discuss upper bounds for Transformers for specific tasks relevant to practice. In Section F, we show Transformers can represent a broader class of Boolean functions which include subclasses like k-CNFs/k-DNFs. Our lower bounds for multi-layer RNNs and 1-layer Transformers apply to any function with communication complexity ~ N, including most Boolean functions. Since the work aims to understand the problems theoretically, the problems must be mathematically well-defined and hence synthetic by definition. We're unsure what is meant by "other domains," but as these models are applied to more domains beyond NLP, like formal mathematics or algorithm design, understanding their capabilities/limitations along the lines we have considered in our paper would be imperative. We hope the techniques/framework presented in our work will be useful for such analyses.

Thank you for your thoughtful comments and time.

Responses to the individual comments below.

“I believe that the authors could further improve the presentation of their results. In particular, it is not clear at the beginning why they choose the tasks they propose and it sounds a bit like a "catalog". I think the authors should clearly say that they consider a case where a 1-layer transformer with log(L) params fail but not RNN, another case where RNN with log(L) params fail but not a 1-layer etc. Maybe it may be worth adding a table where the column headers are the tasks and the row headers are the two models and each entry contains the complexity of each model at each task.”

Thank you for the suggestion. We agree that categorizing with respect to the separations (log L vs L) could be more helpful. We considered adding a table/figure at the top of the second page. We weren’t sure about the best way to depict the results and due to lack of space, we decided to go without it. We will consider adding these in the next version.

“Besides, I liked a lot the discussion from lines 210 to 218 and I believe that this should be earlier in the paper (even in the introduction). I think this point is central to understand one difference between Transformers and RNNs. I think that the point raised by the authors is not totally novel since a similar behavior has been reported by [1] in the case of the copy task.”

Thanks for the suggestion and we will consider adding it to the introduction in the next version. Regarding your point about [1], we do not claim novelty about the intuition. We believe other researchers in the community may have a similar intuition behind the differences in the two architectures. In our work, that intuition is formalized using communication complexity for lower bounds and the JL vectors for upper bounds. In their work [1], they use a different approach to derive a lower bound for the copying task. However, it is worth noting that using communication complexity-based techniques as used in our work, it is also possible to show lower bounds for RNNs to perform the copying task. We will consider adding that somewhere in the appendix for readers who might find it interesting.

“Regarding the superiority of RNNs over Transformers in the case of the bounded Dyck languages, do the authors have a similar discussion to add? If yes, could they add it? Is the explanation similar to the one advanced by [2]?”

We have some discussion on this at the beginning of Section F, which you might find helpful. However, the discussion is intertwined with the proof technique, so it might be less straightforward than the former discussion. The general intuition is that bounded Dycks can be represented by constant-sized DFAs, implying that RNNs require very little (constant) memory while processing them sequentially. In contrast, a 1-layer Transformer must compute the same based on a convex combination of all input symbols (attention) and classify 0 or 1 based on this vector (using MLP). The weights of the convex combination are determined by dot products of query and key projections, and hence cannot be arbitrary.

In simpler terms, the proof intuitively shows that if a 1-layer Transformer can recognize bounded Dyck languages, then the query and value vectors must contain sufficient information, $\Omega(N)$ in bits. Think of it this way: the width of the query/key vectors determines the flexibility of the attention weights, and the width of the value vectors or input embeddings determines the amount of information stored in the output of the attention block. The proof essentially shows that both must be sufficiently wide (contain enough bits of information) for any arbitrary MLP block to be able to classify correctly based on the attention block's output.

“Lastly, I don't know if it is possible to give any intuition about the limitation of 1-layer Transformers and RNNs at representing boolean functions?”

For RNNs, even for Boolean functions, the key intuition is the same as the one explained for the Index Lookup task. The goal of introducing that task was to highlight that intuition in a natural manner since it may be less obvious in the context of Boolean functions. For 1-layer Transformers, the intuition is the same as the one described above.

“I am not sure to follow the experiments for the bounded Dyck languages. The authors say that the 1-layer Transformer achieve near perfect accuracy up to lengths 100 but the red curve in figure 2 right is around 60% for all the iterations. Did I miss something?”

For bounded Dyck languages, we find that 1-layer Transformers struggle at lengths 200 and above, unlike RNNs and 2-layer Transformers. Figure 2 right depicts the validation curve for models at length 400 (and not 100). The goal of that line about lengths 100 is to clarify that this difference is performance occurs at lengths above 100 or so which is natural since the difficulty of the tasks increases with length. For the Index Lookup task, all models solve the task at length 20 and the difference is more stark at length 100 and above (see Figure 2 left).

Thank you for your thoughtful comments and time.

Responses to the two points raised in your review below.

“In particular, for the index lookup task, it makes sense that the only way RNNs can retrieve the symbol $s_p$ at an unknown location revealed at the end is only via storing all the past information in its hidden state and hence $m\geq N/p$ is logical. However, if you feed the sequence in the order $p, s_1,\ldots, s_N$, would the same result hold? I believe you could get away with $\log N$ here too though I could be wrong. Shedding light on things like this could yield more insights about how these architectures are fundamentally different? Because for an index lookup task, if all we care about is retrieving a symbol at some position, we don't really care about which order you feed the input sequence right?”

While what you have mentioned is technically correct, that approach is specific to the particular version of the Index Lookup task and it does not overcome the fundamental issues with how RNNs process inputs.

To be clear, for the case where the models are provided sequences in the order $p, s_1,\ldots, s_N$, RNNs can indeed get away with a hidden state of size $\log N$. However, consider the following variant of the Index Lookup task (let’s call it Multi-Index Lookup) where the models are provided with $k =O(N)$ (e.g. N/2, N/4, etc) indices for which they have to look up and produce the respective symbols. In particular, the input is $s_1, \ldots, s_N, p_1, p_2, \ldots, p_{k}$. For each $p_i$ after the symbols $s_1, \ldots, s_N$, the model is required to output the respective symbol at position $p_i$. Note that for one-layer Transformers, the construction for the Index Lookup task can be directly extended for this Multi-Index Lookup task implying that poly-log size Transformers can solve this.

However, for RNNs, they must have a hidden state of size $\Omega(N)$ to solve this correctly even if the positions are prepended to the symbols. Instead of a reduction from the $\mathrm{Index}$ problem, we can show via a simple reduction from the Disjointness problem. In other words, if the input sequence is of the form $p_1, p_2, \ldots, p_{k}, s_1, \ldots, s_N, p_1, p_2, \ldots, p_{k}$ and an RNN can produce the required outputs then two parties Alice and Bob can compute Disjointness using $mp$ bits which implies that $mp$ must be $\Omega(N)$.

The argument is quite straightforward. Let’s say Alice and Bob have two bits strings $a$ and $b$ of size $k=O(N)$ and both have access to the same RNN. For simplicity, they have agreed that Alice will place her bits in the first $k$ indices sequentially. Alice can then take an RNN, and provide it with indices $1$ to $k$ as input followed by $k$ symbols corresponding to $a$. The last $N - k$ symbols can be arbitrary. Alice can then send the hidden state to Bob which requires $mp$ bits. Bob can provide the same set of indices $1$ to $k$ to the RNN and then record the output. Bob can then compute Disjointness and hence it follows that $mp= \Omega(N)$.

Summary: While it is true that for the Index Lookup task prepending the input sequence with the position/indices can make a difference for RNNs, the limitation/lower bound still applies for a natural extension of the task involving multiple indices. For us, the goal of introducing the Index Lookup was to come up with the simplest task to describe our tools. However, based on the point raised by you, we see that it could create confusion, and will make sure to clarify this in the next version of the paper.

“I realized that the soft-max attention in line 121 is non-causal. Would your results change if it's causal attention?”

Using causal attention does not affect any of the constructions or lower bounds for Transformers in the main paper, i.e., Index Lookup, Equality, Disjointness, Nearest Neighbor, etc. It only affects the construction of Transformers presented in Section F.3 for a more abstract yet general class of Boolean functions.