When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective

We thank the reviewer for their thoughtful evaluation and positive feedback, and address their questions and concerns below.

• The fact that Transformers are better than RNNs and RNNs are better than FFNs seems intuitive for the task at hand:

  We would like to highlight that our contribution is exactly to mathematically formalize this separation in a quantifiable way. To our knowledge, we are the first to theoretically prove a sample complexity separation between Transformers/RNNs/FFNs, and we further believe that the proof techniques we develop to establish these separations can be useful in subsequent studies of other/combined architectures.

• The paper is a bit difficult to read:

  Thank you for this feedback. Table 1 and Theorem 1 summarize exactly how much Transformers are better than RNNs (on all of qSTR) and RNNs are better than FFNs (on simple-qSTR). We will try to improve the readability of the paper before the final version, and would be happy to incorporate any further specific feedback on improving readability.

• Why is qSTR relevant? Where is the general form useful compared to the simpler variant?:

  We believe this is an important question, also raised by Reviewer J2MZ, and plan to incorporate such an example to highlight the relevance of qSTR in practice.

  Input string: For my vacation this summer, I’m considering either Rome, Paris, or Tokyo. If I go to Rome, I would like to see their historic sites, if I go to Paris, I want to visit their art museums, and if I end up in Tokyo, I want to try their cuisine. Can you tell me how much my second option would cost? Would it cost more than the third option?

  Here, the token second determines that the important tokens to process are Paris and art museums, and the token third determines that the important tokens are Tokyo and cuisine. Namely, the task involves both retrieving a few important tokens from all tokens, and processing them.

  We remark that our qSTR model is of course a simplification of this setting, and it most importantly serves as a theoretical benchmark used by prior works, see e.g. [SHT23, WWHL24].

  The difference between qSTR and simple-qSTR lies in the fact that the former is a sequence-to-sequence mapping, while the latter is a sequence-to-scalar mapping (i.e. all elements in the output sequence are identical). One way to illustrate this difference is to view qSTR as answering multiple questions about the prompt where the number of questions and thus the output of the model also grows with the input length, while viewing simple-qSTR as answering a single question, thus having an effectively constant-length output. We will better emphasize this difference in the final version.

• What would happen if the number of queries is also dynamic?:

  This is an interesting question. In this case, one would need to encode a list of indices of different lengths, which is less straightforward. Further, one would need to define how a unique function $g$ can act on sequences of different lengths. However, once these technical aspects are resolved, one might be able to show that the fundamental learning mechanism of Transformers for this problem remains unchanged.

• What happens if qSTR is made causal?:

  We note that qSTR not being causal is exactly why we use bidirectional RNNs. We expect that if one considers a causal restriction of qSTR, then Transformers with causal masks and single-directional RNNs can learn it.

• What is the intuition behind Assumption 1?:

  Assumption 1 is needed for purely technical reasons (to establish concentration bounds), and is very mild compared to typical data assumptions in the literature. It essentially means that $\Vert \boldsymbol{x}\Vert$ is subGaussian, and $y$ is sub-Weibull (even milder than sub-exponential). In practice these assumptions are usually satisfied as these quantities are typically bounded. We will further clarify this in the revised version.

• Discussion of limitations:

  Thank you for pointing this out. We will better highlight the limitations of our work in the final version. Specifically, our main limitation is the dependence of the lower bounds to ERM instead of being algorithm-free, and it would be interesting to see techniques developed to obtain minimax lower bounds for RNNs/FFNs over larger classes of algorithms. While another limitation can be the lack of studying optimization dynamics for Transformers, we believe this part should be more doable as the optimization dynamics of similar problems have been analyzed in the literature [WWHL24].

We would be happy to answer any follow-up questions.

References:

[SHT23] C. Sanford et al. “Representational strengths and limitations of transformers”. NeurIPS 2023.

[WWHL24] Z. Wang et al. “Transformers provably learn sparse token selection while fully-connected nets cannot.” ICML 2024.

We thank the reviewer for their thoughtful evaluation and positive feedback, and address their questions and concerns below.

• The Transformer model studied is restricted to a single-layer architecture / How to extend to deeper Transformers:

  When considering the $q$STR model, it would be relatively straightforward to prove that a multi-layer Transformer can also learn sample-efficiently, where the subsequent layers simply learn an identity map.

  We however agree that an interesting open problem is to find data models where there exists a depth separation, and one needs deep Transformers to learn sample-efficiently. There are certain tasks for which Transformer depth lower bounds are known [SHT24, CPW25]. However, these lower bound arguments are based on communication complexity and hold for finite-bit precision. It would be an interesting direction for future work to find representational lower bounds that eventually characterize sample complexity.

• The empirical experiments, though illustrative, are limited in scope and conducted on synthetic tasks:

  Indeed, our main contributions are theoretical and we present the numerical experiments only to validate our theory, and to demonstrate that our theoretical constructions for Transformers match the result of optimization algorithms, thus our ERM upper bounds should extend to gradient-based optimization.

  We agree that it is important to have real-world examples where one can empirically verify Transformers outperform RNNs/FFNs on similar recovery problems. We remark however that the empirical separation between Transformers and RNNs/FFNs on this type of information retrieval tasks has already been well-studied in the literature [JBKM24]. We will better highlight these empirical separations in the revised version of our manuscript.

• Paper Formatting Concerns:

  Thank you for your suggestions.

We would be happy to answer any follow-up questions.

References:

[SHT24] C. Sanford et al. “Transformers, parallel computation, and logarithmic depth.” ICML 2024.

[CPW25] L. Chen et al. “Theoretical limitations of multi-layer Transformer.” FOCS 2025.

[JBKM24] S. Jelassi et al. “Repeat After Me: Transformers are Better than State Space Models at Copying.” ICML 2024.

We thank the reviewer for their thoughtful evaluation and positive feedback, and address their questions and concerns below.

• Experiments are done on 1-STR:

  Indeed, we choose 1-STR as the simplest baseline and still observe the theoretical separation in practice. We believe that this separation would be even more pronounced for larger values of $q$, and plan to include such experiments in the final version of the manuscript.

• Some factors for logical flow requires readers to refer to appendices:

  Thank you for this feedback. We will try to improve the readability of our manuscript before the final version.

• Do you expect RNNs with attention mechanism will address some of the issues noted in the paper?:

  Yes, we believe an interesting future direction is to theoretically study the capabilities of hybrid architectures that can achieve some notion of optimal tradeoff by combining some global and local information.

• Will the result of Figure 2, the standard optimization of Transformer, match the theoretical construction, even for general multi-head cases?:

  This is an interesting question and we will perform additional experiments before the final version of our manuscript to see if this phenomenon holds for $q \geq 1$ where we need to use multiple heads.

• Explicit mentioning of the limitation about the potential gap between theoretical analyses given by ERM and the empirical training done by gradient descent:

  We thank the reviewer for this suggestion which will help readers better understand the current state of theoretical results on Transformers and our contributions, we will clarify this gap in the final version.

• Paper Formatting Concerns:

  Thank you for expressing your concern. We adopt the amsalpha citation style from natbib that is quite common among theoretical works in NeurIPS, specifically to be consistent with this literature.

We would be happy to answer any follow-up questions.

We thank the reviewer for their thoughtful evaluation and positive feedback, and address their questions and concerns below.

• The qSTR model may be overly simplified compared to real-world language tasks.

  We agree with the reviewer that this model is a simplification of real-world dependencies. Our motivation to view this model was to use it as a theoretical benchmark following the works of [SHT23] and [WWHL24]. However, we will provide the following example to better demonstrate the relevance of qSTR in real-world language modeling:

  Input string: For my vacation this summer, I’m considering either Rome, Paris, or Tokyo. If I go to Rome, I would like to see their historic sites, if I go to Paris, I want to visit their art museums, and if I end up in Tokyo, I want to try their cuisine. Can you tell me how much my second option would cost? Would it cost more than the third option?

  Here, the token second determines that the important tokens to process are Paris and art museums, and the token third determines that the important tokens are Tokyo and cuisine. Namely, the task involves both retrieving a few important tokens from all tokens, and processing them.

  We hope this example clarifies the relevance of the qSTR model, and plan to include such an example in the final version of our paper.

• It remains unclear whether Transformers trained via standard optimization algorithms can effectively discover the constructive attention patterns in the theoretical analysis:

  Indeed, this is an important problem. We would like to highlight that we provide some empirical evidence in Figure 2 that our attention construction is indeed learned by AdamW. Further, [WWHL24] have studied the optimization aspect and were able to theoretically prove that gradient-based optimization recovers the same construction. However, their analysis is in the population limit, and we leave the analysis of finite-sample gradient-based optimization to future work, which we believe should be within reach given the current theoretical tools.

• How sensitive are the conclusions to the embedding dimension?:

  The lower bound on the number of heads holds for any embedding dimension, and is in fact an approximation lower bound, meaning that even with infinite embedding dimension and infinite number of samples, the Transformer still cannot learn the qSTR model unless $H \geq \Omega(q)$.

  On the other hand, a larger embedding dimension may be detrimental to generalization and increase the number of training samples needed. However, depending on the way the embedding is defined, one might be able to find tailored generalization arguments that avoid a worse dependency. In particular, one should avoid using one-hot encoding for positions, as the embedding dimension would grow linearly with the sequence length which is not ideal for this setting.

We would be happy to answer any follow-up questions.

References:

[SHT23] C. Sanford et al. “Representational strengths and limitations of transformers”. NeurIPS 2023.

[WWHL24] Z. Wang et al. “Transformers provably learn sparse token selection while fully-connected nets cannot.” ICML 2024.