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

We sincerely thank Reviewer U9LY for the detailed and thoughtful feedback on our paper. We are delighted that you found the manuscript well-written, well-referenced, and addressing significant questions about the limitations of current architectures for sequence modeling. Your insights have been highly constructive, and we are grateful for the opportunity to improve/rewrite our work based on your suggestions.

---

Addressing Weaknesses

1. Providing Additional Background on Communication Complexity

We appreciate your recommendation to improve the accessibility of our manuscript by providing more background on communication complexity. To address this, we will make the following changes in the revised paper:

• Introduction of Key Concepts: We will include a high-level, intuitive explanation of communication complexity, covering core ideas like communication protocols, the pointer chasing problem, and their relevance to sequence modeling.
• Background on Relevant Problem Classes: The revised paper will provide additional context for computational classes such as $\mathbf{L}$ (logarithmic space) and $\mathbf{NL}$ (nondeterministic logarithmic space), explaining their role in characterizing the challenges faced by sequence models.

These additions will ensure that readers without a computational complexity background can better understand the motivations and implications of our work.

---

2. Bridging the Gap Between Theory and Practice in Computational Complexity

We value your observations about the discrepancies between theoretical constructs and practical applications. Below, we address your specific questions:

(a) What aspects of the formal definitions might be overly general with respect to practical settings?

The following assumptions in our theoretical framework contribute to potential overgeneralization:

• Worst-Case Analysis: Theoretical results often reflect worst-case scenarios, which may not represent the typical distributions of real-world data.
• Simplified Architectures: We consider simplified architectures for analytical tractability, omitting practical enhancements such as optimized attention mechanisms or regularization strategies.
• Deterministic Computation: Our theoretical results assume deterministic computations, overlooking stochastic elements like dropout and random initialization.
• Perfect Inputs: Our analysis does not model Real-world data imperfections (e.g., noise, errors).

But, since models are proven to be limited even in these idealized cases, they will struggle even more in practice when there is more stochasticity.

(b) Could discrepancies between formalization and practice account for the observed results? Yes, these discrepancies might explain some of the divergence between theoretical and practical performance. However, our empirical findings suggest that theoretical limitations remain relevant:

• Performance Degradation: Tasks requiring deep compositional reasoning showed significant performance degradation, aligning with our theoretical predictions.
• Error Patterns: Failure modes observed in practice are consistent with our identified theoretical constraints.

(c) What empirical work could help bridge this gap? To close the gap between theory and practice, we propose the following empirical strategies:

• Controlled Experiments: Design benchmarks tailored to theoretical limitations, allowing for direct empirical validation.
• Ablation Studies: Investigate how specific architectural components and training strategies impact model performance on theoretical tasks.
• Error Analysis: Conduct detailed examinations of failure cases to uncover reasoning bottlenecks in models.
• Cross-Model Comparisons: Compare various architectures (e.g., RNNs, Transformers, and SSMs) to identify universal versus architecture-specific limitations.
• Real-World Task Evaluation: Assess models on real-world problems requiring compositional reasoning to determine practical applicability.
• Benchmark Development: Establish standardized datasets and tasks to improve broader comparisons and progress tracking.
• Theory-Informed Experiments: Use theoretical insights to design experiments that test specific hypotheses about model limitations.

Although we included most of them, these initiatives would promote a deeper understanding of the interplay between theoretical constraints and practical model performances. They can be interesting follow-up work. Thank you for pointing out this direction.

---

Addressing Specific Comments and Suggestions

Formatting Error in Section 7 Heading

Thank you for identifying this oversight. We will fix the spacing issue to ensure the heading is properly formatted.

Relocating the "Implications for General Artificial Intelligence" Paragraph

We appreciate your suggestion to improve the flow of this discussion. We will relocate this paragraph to a dedicated "Implications" section or incorporate it into the "Conclusion" to improve the paper's structure.

---

Thank you once again for your valuable feedback. We are confident these revisions will make our work better and more accessible to the community.

We sincerely thank the reviewer for their thoughtful feedback and insightful suggestions. We appreciate acknowledging our work’s originality, clarity, and significance in exploring the limitations of reasoning abilities in Structured State Space Models (SSMs) and Transformers. Below, we address the reviewer’s queries and expand on their recommendations.

---

1. Additional Section on Limitations and Future Work

Comment: Could the authors provide an additional section on limitations (of this work per se) and future works that practitioners may follow? For example, could the authors discuss more specific architectural modifications based on the existing results?

Response:

We acknowledge the importance of delineating the limitations of our work and outlining potential directions for future research. Below, we address these in detail:

Limitations of Our Work

1. Focus on Current Architectures: Our theoretical and empirical analyses are restricted to existing SSM and Transformer architectures. We did not explore architectural modifications or external enhancements that might expand their reasoning capabilities.

2. Idealized Assumptions: The theoretical results are derived under standard complexity-theoretic and algorithmic assumptions. These abstractions do not fully account for practical factors such as optimization dynamics, hardware constraints, or domain-specific training regimes.

3. Scope of Empirical Evaluation: While we conducted extensive experiments across diverse tasks, our exploration is not exhaustive. Alternative configurations, training paradigms, or specific domain-focused benchmarks could reveal additional insights.

---

Future Work and Potential Architectural Modifications

Building on our findings, we identify the following directions for future research:

1. Integrating External Memory Mechanisms:

   • Incorporating memory-augmented components, such as differentiable neural computers or external attention mechanisms, could enable models to effectively store and retrieve intermediate computations.
   • This approach could mitigate existing multi-step reasoning and function composition limitations by allowing models to scale reasoning over extended sequences. While this improves general reasoning capabilities, it may remain insufficient for problems demanding deeper algorithmic understanding (e.g., solving unsolved mathematical conjectures).

2. Incorporating Symbolic Reasoning Components:

   • Hybrid architectures that combine neural networks with symbolic reasoning frameworks (e.g., integrating SAT solvers or formal theorem provers) may improve models’ logical inference capabilities.
   • Symbolic modules can complement neural systems by performing exact computations, thus addressing the constraints of neural-based architectures in handling structured, logical reasoning.

3. Implementing Specialized Training Strategies:

   • Designing tailored training paradigms, such as curriculum learning or meta-learning approaches, could enable models to progressively develop reasoning skills.
   • Auxiliary tasks emphasizing multi-step reasoning or function composition might also facilitate improved generalization to complex tasks.

4. Exploring Alternative Computational Frameworks:

   • Investigating architectures inspired by computational models with theoretically higher capacities (e.g., hypergraph-based neural networks or quantum-inspired architectures) could unlock new pathways for complex reasoning.
   • Such frameworks may inherently support reasoning-intensive tasks without requiring impractical resource scaling.

5. Advancing Neural Algorithmic Reasoning:

   • Neural Algorithmic Reasoning, an emerging paradigm that aims to align neural networks with classical algorithmic processes, presents a promising avenue.
   • By embedding algorithmic structures into neural systems, these models can execute complex computations over large domains (without requiring impractically large state dimensions or excessive computational resources), enabling capabilities such as iterative function composition, mathematical problem-solving, and logical deduction.
   • Leveraging this approach can address the architectural and training bottlenecks identified in our study, offering a robust framework for tackling reasoning-centric tasks.

---

Dear Reviewer, thank you for your thorough and insightful review of our paper. We appreciate your constructive feedback and have carefully considered each of your points. Before the deadline, we will update the manuscript.

---

Responses to Questions:

1. Questions about Theorem 1:

Question 1:

The proof seems to rely on the specific ordering of g followed by f followed by x in the prompt. Does a similar proof work when these pieces are in different orders? In particular, what about the order that would intuitively be the easiest for the SSM: x followed by g followed by f? (The intuition here comes from the fact that a streaming algorithm taking in (x, g, f) in this order wouldn't need to store the entire table of f or g.)

Response:

You are correct that the ordering of the prompt in our proof plays a role in the communication complexity argument. However, the fundamental limitation does not depend on the specific order of x, g and f in the prompt.

In our initial proof, we assumed a prompt where the descriptions of g and f precede the query x. This aligns with how we constructed the communication protocol to simulate the SSM's computation.

We can adapt the proof accordingly if the prompt order is x followed by g followed by f. The key challenge remains: to compute f(g(x)) over large domains without storing substantial information about f and g is fundamentally difficult for SSMs due to their limited state size.

Even if x is presented first, the SSM must retain x while processing g and then f. Since g and f are arbitrary functions over large domains, the model must still capture significant information about them to compute f(g(x)). This requires a substantial state size, regardless of the prompt order.

Therefore, the limitations we proved still hold under different prompt orderings. We will revise the proof in our paper to clarify that the argument applies regardless of the order of x, g, and f in the prompt.

Edits to the Manuscript:

• Section 4 (Function Composition Requires Wide One-Layer Models): We will revise the proof of Theorem 1 to explicitly address different prompt orderings. We will demonstrate how the communication complexity argument can be adapted to various prompt structures, reinforcing that the fundamental limitation arises from the need to represent large functions, not from the specific prompt order.

---

2. Questions about Theorem 2:

Question 2:

How is the definition of CoT different from just autoregressive decoding?

Response:

Thank you for highlighting the need for clarification. In our definition, the Chain-of-Thought (CoT) refers to a model generating intermediate reasoning steps that explicitly break down the problem-solving process. While autoregressive decoding involves predicting the next token based on previous tokens, CoT is designed to encourage the model to produce a sequence of logical reasoning steps leading to the final answer.

The key differences are:

• Purpose: CoT aims to mimic human-like reasoning by generating intermediate steps that make the model's thought process explicit.

• Structure: In CoT, the model is prompted or trained to produce these reasoning steps, which may involve additional tokens that represent sub-calculations or explanations.

• Autoregressive Decoding: While CoT uses autoregressive decoding as the mechanism to generate the sequence, not all autoregressive decoding involves CoT. Standard autoregressive models may generate outputs without explicit intermediate reasoning.

In our paper, we defined CoT within the context of SSMs by formalizing how the model recursively generates additional tokens based on its previous outputs and inputs, focusing on the reasoning aspect.

Edits to the Manuscript:

• Section 5 (Many Thought Steps are Needed): We will update the definition of CoT to clearly distinguish it from standard autoregressive decoding. We will emphasize the role of intermediate reasoning steps in CoT and explain how it simulates multi-step reasoning processes, making the distinction more explicit.

---

3. Questions about Theorem 4:

Question 3:

Lines 74 & 386: Isn't L a class of decision problems? Shouldn't one say FL instead of L here?

Response:

You are correct. In computational complexity, L refers to the class of decision problems solvable in logarithmic space, while FL denotes the class of function problems computable in logarithmic space. Since our focus is on function computation rather than decision problems, it is more precise to refer to FL.

Edits to the Manuscript:

• Throughout the Paper: We will replace L with FL when referring to function computation in logarithmic space. This change will improve the precision of our statements regarding the computational complexity classes involved.

---

I thank the authors for their detailed response and explanations.

1. I look forward to seeing the strengthened theorem statement. I would be appreciate it if it can be provided before the end of the discussion period.

2. I appreciate the informal explanation of the difference between CoT and autoregressive decoding, but my question was specifically about the formalization of CoT given in the paper. You say "we defined CoT within the context of SSMs by formalizing how the model recursively generates additional tokens based on its previous outputs and inputs", which is in agreement with my understanding of your definition. However, to me, that definition seems to be an accurate formalization of autoregressive decoding without incorporating the reasoning aspects of CoT.

3. Making the changes to replace $\mathsf{L}$ with $\mathsf{FL}$ sounds good to me.

I'm looking forward to the authors' responses to my questions 2-6 regarding Theorem 4.

Dear Reviewer yPps,

1. We are very grateful for your insightful review. Your feedback has been instrumental in strengthening and changing Theorem 4. We have addressed all of your questions (points 2 to 6) by improving Theorem 4 and adding relevant explanations in the text following Theorem 3 and before the Experiments section. These updates are included in the revised manuscript.

2. You are correct in noting that we do not utilize external assistance in the "reasoning" process. This clarification aligns with the point raised by Reviewer BvEu, who initiated the discussion regarding AlphaProof-based external systems. If our paper is accepted, we will include a few additional sentences in the camera-ready version to further clarify and eliminate any ambiguity on this matter.

3. Thank you once again for your valuable observation. We did not put assumptions on A_t, B_t, C_t, and D_t since we now changed Theorem 4. Log assumptions had to be initially made, as in [1] on Page 6, Lemma 4.1.

[1] The Illusion of State in State-Space Models; William Merrill, Jackson Petty, Ashish Sabharwal

1

I appreciate the authors' update to Theorem 4. The update resolves Question 2 that I had, and also renders my Questions 3-5 obsolete since the entire theorem statement was changed.

Maybe putting the original Theorem 4 in the Appendix would be nice, and you can state in the main text "Under the log-precision assumption from Merrill et al. 2024, we prove Appendix Theorem ... that shows .... Here, we show using the more realistic assumption that precision doesn't depend on input sequence length that ..."

The concern in my Question 6 remains. To quote one sentence from my original question:

My computer has finite memory, so does that mean it can only decide regular languages?

The new Theorem 4 is identical in spirit to a theorem (call it Theorem 4') that says "A computer with finite memory is fundamentally limited to computations that can be performed by an FSM." And applying the takeaway in lines 426-431 to Theorem 4' will look like this:

These limitations are significant because they highlight the boundaries of what computers can achieve in practical settings. Regarding practical considerations, since real-world implementations of computers operate on hardware with finite memory and finite precision arithmetic, these theoretical limitations directly apply to computers used in actual applications. Therefore, when designing systems for tasks that require processing beyond regular languages, it becomes clear that computers may not suffice, and alternative architectures or computational mechanisms need to be considered to overcome these inherent constraints.

which is the incorrect takeaway. The correct takeaway from Theorem 4' is that, although real computers operate with finite memory, the aptest theoretical model is one with infinite memory (i.e., a Turing machine). Similarly, I believe that the correct takeaway from the new Theorem 4 is that, although real SSMs operate with finite precision, the aptest theoretical model is one with infinite precision.

2

Although the added paragraph in the paper does not directly address my question, I accept the formalization of CoT purely based on the fact that it was based on prior work. (However, I maintain that the formalization better captures the idea of autoregressive decoding and not of CoT.)

3

Your definition of SSMs allows the matrices $A_t, B_t, C_t, D_t$ to depend on $t$, but your proof of Theorem 4 assumes fixed $A, B, C, D$. I would recommend explicitly stating this assumption in the theorem statement.

About Theorem 1

I appreciate the updated theorem and believe it is stronger than the previous one, although I have not yet checked the details of the proof.

Summary

I have revised my Soundness Score to 2 and Overall Score to 5 (Weak Reject).

• Explanation for not higher score: As elaborated above, my concern raised in Question 6 remains unresolved.
• Explanation for increase in score: Question 2 was resolved with the more realistic model of fixed precision. Also, although I would still recommend rejection based on my unresolved Question 6 alone, my objection is reduced by the fact that the authors are following the finite-precision assumption of previous work.

I very much thank the authors for engaging in productive discussions about their paper. From the start to the end of the discussion period, I increased my score from 3 (reject) to 6 (borderline accept).

A few of my questions and concerns have been addressed, and the main concern remaining pertains to the practical implications of Theorem 4. Assuming that the authors will address my current concerns that version 2 of the manuscript oversells the implications of the result, I recommend weak acceptance of the paper.

Sincerely,

Reviewer yPps

We sincerely thank the reviewer for their positive feedback and highlighting our paper's contributions. Below, we address your suggestions regarding comparisons to prior work and the relationship between numerical experiments and theoretical results.

---

Comparing Our Results to Peng et al.

Comment: No real weakness. Potentially authors could spend more time comparing their results to Peng for readers.

Response:
We agree that a detailed comparison with Peng et al. would aid readers. Here’s a concise summary of distinctions and extensions provided by our work:

1. Architectural Scope:

   • Peng et al. focused on Transformers, showing limitations in function composition over large domains.
   • We extended this analysis to Structured State Space Models (SSMs), proving that they also struggle with function composition without exponential state dimensions, suggesting broader limitations across sequence models.

2. Theoretical Contributions:

   • Peng et al. placed Transformers in weak complexity classes, showing their inefficiency in compositional reasoning.
   • We showed that multi-layer SSMs operate within $L$ (logarithmic space), reinforcing their computational constraints and inability to solve $NL$-complete problems unless $L = NL$.

3. Chain-of-Thought (CoT) Analysis:

   • Peng et al. highlighted exponential scaling in reasoning steps with CoT prompting for Transformers.
   • We demonstrated similar limitations for SSMs, with CoT requiring insufficient polynomially growing steps to overcome inherent architectural constraints.

4. Empirical Evidence:

   • Both works showed limitations in function composition tasks, but our experiments confirmed that SSMs face similar barriers despite their distinct architectural design, along with many more experiments in the appendix.

Summary:
Our findings complement Peng et al.’s work by generalizing their insights to SSMs, reinforcing that these limitations are not specific to Transformers but reflect fundamental constraints in sequence modeling architectures.

---

Clarifying the Relationship Between Numerical Experiments and Theoretical Results

Comment: Authors could clarify the numerical experiments and their relationship to the main theorem with respect to layer number.

Response:
Our numerical experiments were designed to validate the theoretical results, particularly Theorem 3, which places $L$-layer SSMs in $L$ (logarithmic space). Key findings include:

1. Layer Depth and Performance:

   • Increasing SSM depth improved performance marginally but plateaued quickly, consistent with the theoretical prediction that computational capacity does not scale significantly with depth.

2. Function Composition Tasks:

   • Deeper SSMs did not overcome limitations in multi-step reasoning or function composition, aligning with our proof that they remain constrained by $L$.

3. Chain-of-Thought Prompting:

   • CoT prompting aided SSMs but required polynomial growth in reasoning steps. Additional layers did not alleviate this growth, reinforcing that the architectural constraints persist despite CoT.

Conclusion:
These experiments support our theoretical results, demonstrating that SSM limitations stem from fundamental architectural constraints, not just depth.

---

We appreciate the reviewer’s thoughtful suggestions and hope these clarifications improve the understanding. We remain open to further questions and would be grateful if these responses are satisfactory enough to warrant an updated score.