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

Understand

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.