The Expressive Capacity of State Space Models: A Formal Language Perspective

• URL: http://arxiv.org/abs/2405.17394v2
• Date: Sun, 2 Jun 2024 19:43:55 GMT
• Title: The Expressive Capacity of State Space Models: A Formal Language Perspective
• Authors: Yash Sarrof, Yana Veitsman, Michael Hahn,
• Abstract summary: recurrent models based on linear state space models (SSMs) have shown promising performance in language modeling (LM), competititve with transformers. We present a comprehensive theoretical study of the capacity of such SSMs as it compares to that of transformers and traditional RNNs.
• Score: 0.8948475969696075
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently, recurrent models based on linear state space models (SSMs) have shown promising performance in language modeling (LM), competititve with transformers. However, there is little understanding of the in-principle abilities of such models, which could provide useful guidance to the search for better LM architectures. We present a comprehensive theoretical study of the capacity of such SSMs as it compares to that of transformers and traditional RNNs. We find that SSMs and transformers have overlapping but distinct strengths. In star-free state tracking, SSMs implement straightforward and exact solutions to problems that transformers struggle to represent exactly. They can also model bounded hierarchical structure with optimal memory even without simulating a stack. On the other hand, we identify a design choice in current SSMs that limits their expressive power. We discuss implications for SSM and LM research, and verify results empirically on a recent SSM, Mamba.

Related papers

• Provable Benefits of Complex Parameterizations for Structured State Space Models [51.90574950170374]
  Structured state space models (SSMs) are linear dynamical systems adhering to a specified structure. In contrast to typical neural network modules, whose parameterizations are real, SSMs often use complex parameterizations. This paper takes a step towards explaining the benefits of complex parameterizations for SSMs by establishing formal gaps between real and complex diagonal SSMs.
  arXiv  Detail & Related papers  (2024-10-17T22:35:50Z)
• On the Adversarial Transferability of Generalized "Skip Connections" [83.71752155227888]
  Skip connection is an essential ingredient for modern deep models to be deeper and more powerful. We find that using more gradients from the skip connections rather than the residual modules during backpropagation allows one to craft adversarial examples with high transferability. We conduct comprehensive transfer attacks against various models including ResNets, Transformers, Inceptions, Neural Architecture Search, and Large Language Models.
  arXiv  Detail & Related papers  (2024-10-11T16:17:47Z)
• Longhorn: State Space Models are Amortized Online Learners [51.10124201221601]
  State-space models (SSMs) offer linear decoding efficiency while maintaining parallelism during training. In this work, we explore SSM design through the lens of online learning, conceptualizing SSMs as meta-modules for specific online learning problems. We introduce a novel deep SSM architecture, Longhorn, whose update resembles the closed-form solution for solving the online associative recall problem.
  arXiv  Detail & Related papers  (2024-07-19T11:12:08Z)
• Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality [31.985243136674146]
  We show that state-space models (SSMs) such as Mamba have been shown to match or outperform Transformers at small to medium scale. Our state space duality (SSD) framework allows us to design a new architecture (Mamba-2) whose core layer is an a refinement of Mamba's selective SSM that is 2-8X faster.
  arXiv  Detail & Related papers  (2024-05-31T17:50:01Z)
• State Space Models are Comparable to Transformers in Estimating Functions with Dynamic Smoothness [41.617269918948686]
  Deep neural networks based on state space models (SSMs) are attracting much attention in sequence modeling. This paper theoretically explores in which tasks SSMs can be alternatives of Transformers from the perspective of estimating sequence-to-sequence functions. We prove that SSMs can estimate the target function, even if the smoothness changes depending on the input sequence, as well as Transformers.
  arXiv  Detail & Related papers  (2024-05-29T12:23:48Z)
• State Space Model for New-Generation Network Alternative to Transformers: A Survey [52.812260379420394]
  In the post-deep learning era, the Transformer architecture has demonstrated its powerful performance across pre-trained big models and various downstream tasks. To further reduce the complexity of attention models, numerous efforts have been made to design more efficient methods. Among them, the State Space Model (SSM), as a possible replacement for the self-attention based Transformer model, has drawn more and more attention in recent years.
  arXiv  Detail & Related papers  (2024-04-15T07:24:45Z)
• The Illusion of State in State-Space Models [27.57426601905237]
  State-space models (SSMs) have emerged as a potential alternative architecture for building large language models. We show that SSMs have similar limitations to non-recurrent models like transformers, which may limit their ability to solve real-world state-tracking problems.
  arXiv  Detail & Related papers  (2024-04-12T21:30:06Z)
• Theoretical Foundations of Deep Selective State-Space Models [13.971499161967083]
  Deep SSMs demonstrate outstanding performance across a diverse set of domains. Recent developments show that if the linear recurrence powering SSMs allows for multiplicative interactions between inputs and hidden states. We show that when random linear recurrences are equipped with simple input-controlled transitions, then the hidden state is provably a low-dimensional projection of a powerful mathematical object.
  arXiv  Detail & Related papers  (2024-02-29T11:20:16Z)
• Can Mamba Learn How to Learn? A Comparative Study on In-Context Learning Tasks [25.092302463435523]
  State-space models (SSMs) have been proposed as alternatives to Transformer networks in language modeling. In this study, we evaluate the ICL performance of SSMs, focusing on Mamba, against Transformer models across various tasks.
  arXiv  Detail & Related papers  (2024-02-06T18:56:35Z)
• Repeat After Me: Transformers are Better than State Space Models at Copying [53.47717661441142]
  We show that while generalized state space models are promising in terms of inference-time efficiency, they are limited compared to transformer models on tasks that require copying from the input context.
  arXiv  Detail & Related papers  (2024-02-01T21:44:11Z)
• Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations [51.77000472945441]
  Long Short-Term Memory (LSTM) and Transformers are two popular neural architectures used for natural language processing tasks. In practice, it is often observed that Transformer models have better representation power than LSTM. We study such practical differences between LSTM and Transformer and propose an explanation based on their latent space decomposition patterns.
  arXiv  Detail & Related papers  (2021-12-16T19:56:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.