  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.
