https://arxiv.org/abs/2404.08819

Skip to main content
Cornell University
We gratefully acknowledge support from the Simons Foundation, member
institutions, and all contributors. Donate
 
arxiv logo > cs > arXiv:2404.08819
[                    ]

Help | Advanced Search

[All fields        ]
Search
arXiv logo
Cornell University Logo
[                    ] GO
quick links

  * Login
  * Help Pages
  * About

Computer Science > Machine Learning

arXiv:2404.08819 (cs)
[Submitted on 12 Apr 2024 (v1), last revised 4 Jun 2024 (this
version, v2)]

Title:The Illusion of State in State-Space Models

Authors:William Merrill, Jackson Petty, Ashish Sabharwal
View a PDF of the paper titled The Illusion of State in State-Space
Models, by William Merrill and Jackson Petty and Ashish Sabharwal
View PDF HTML (experimental)

    Abstract:State-space models (SSMs) have emerged as a potential
    alternative architecture for building large language models
    (LLMs) compared to the previously ubiquitous transformer
    architecture. One theoretical weakness of transformers is that
    they cannot express certain kinds of sequential computation and
    state tracking (Merrill & Sabharwal, 2023), which SSMs are
    explicitly designed to address via their close architectural
    similarity to recurrent neural networks (RNNs). But do SSMs truly
    have an advantage (over transformers) in expressive power for
    state tracking? Surprisingly, the answer is no. Our analysis
    reveals that the expressive power of SSMs is limited very
    similarly to transformers: SSMs cannot express computation
    outside the complexity class $\mathsf{TC}^0$. In particular, this
    means they cannot solve simple state-tracking problems like
    permutation composition. It follows that SSMs are provably unable
    to accurately track chess moves with certain notation, evaluate
    code, or track entities in a long narrative. To supplement our
    formal analysis, we report experiments showing that Mamba-style
    SSMs indeed struggle with state tracking. Thus, despite its
    recurrent formulation, the "state" in an SSM is an illusion: SSMs
    have similar expressiveness limitations to non-recurrent models
    like transformers, which may fundamentally limit their ability to
    solve real-world state-tracking problems.

Comments: To appear at ICML 2024. 9 pages + appendices
          Machine Learning (cs.LG); Computational Complexity (cs.CC);
Subjects: Computation and Language (cs.CL); Formal Languages and
          Automata Theory (cs.FL)
Cite as:  arXiv:2404.08819 [cs.LG]
          (or arXiv:2404.08819v2 [cs.LG] for this version)
          https://doi.org/10.48550/arXiv.2404.08819
          Focus to learn more
          arXiv-issued DOI via DataCite

Submission history

From: William Merrill [view email]
[v1] Fri, 12 Apr 2024 21:30:06 UTC (69 KB)
[v2] Tue, 4 Jun 2024 22:05:45 UTC (76 KB)
Full-text links:

Access Paper:

    View a PDF of the paper titled The Illusion of State in
    State-Space Models, by William Merrill and Jackson Petty and
    Ashish Sabharwal
  * View PDF
  * HTML (experimental)
  * TeX Source
  * Other Formats

view license
Current browse context:
cs.LG
< prev   |   next >
new | recent | 2024-04
Change to browse by:
cs
cs.CC
cs.CL
cs.FL

References & Citations

  * NASA ADS
  * Google Scholar
  * Semantic Scholar

a export BibTeX citation Loading...

BibTeX formatted citation

x
[loading...          ]
Data provided by:

Bookmark

BibSonomy logo Reddit logo
(*) Bibliographic Tools

Bibliographic and Citation Tools

[ ] Bibliographic Explorer Toggle
Bibliographic Explorer (What is the Explorer?)
[ ] Litmaps Toggle
Litmaps (What is Litmaps?)
[ ] scite.ai Toggle
scite Smart Citations (What are Smart Citations?)
( ) Code, Data, Media

Code, Data and Media Associated with this Article

[ ] Links to Code Toggle
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
[ ] DagsHub Toggle
DagsHub (What is DagsHub?)
[ ] GotitPub Toggle
Gotit.pub (What is GotitPub?)
[ ] Links to Code Toggle
Papers with Code (What is Papers with Code?)
[ ] ScienceCast Toggle
ScienceCast (What is ScienceCast?)
( ) Demos

Demos

[ ] Replicate Toggle
Replicate (What is Replicate?)
[ ] Spaces Toggle
Hugging Face Spaces (What is Spaces?)
[ ] Spaces Toggle
TXYZ.AI (What is TXYZ.AI?)
( ) Related Papers

Recommenders and Search Tools

[ ] Link to Influence Flower
Influence Flower (What are Influence Flowers?)
[ ] Connected Papers Toggle
Connected Papers (What is Connected Papers?)
[ ] Core recommender toggle
CORE Recommender (What is CORE?)
[ ] IArxiv recommender toggle
IArxiv Recommender (What is IArxiv?)

  * Author
  * Venue
  * Institution
  * Topic

( ) About arXivLabs

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and
share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have
embraced and accepted our values of openness, community, excellence,
and user data privacy. arXiv is committed to these values and only
works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community?
Learn more about arXivLabs.

Which authors of this paper are endorsers? | Disable MathJax (What is
MathJax?)

  * About
  * Help

  * Click here to contact arXiv Contact
  * Click here to subscribe Subscribe

  * Copyright
  * Privacy Policy

  * Web Accessibility Assistance
  * arXiv Operational Status
    Get status notifications via email or slack