The Illusion of State in State-Space Models, William Merrill+, N/A, arXiv'24

[AkihikoWatanabe]

URL

• https://arxiv.org/abs/2404.08819

  Affiliations

  • William Merrill, N/A
  • Jackson Petty, N/A
  • Ashish Sabharwal, N/A

    Abstract

  • State-space models (SSMs) have emerged as a potential alternativearchitecture for building large language models (LLMs) compared to thepreviously ubiquitous transformer architecture. One theoretical weakness oftransformers is that they cannot express certain kinds of sequentialcomputation and state tracking (Merrill & Sabharwal, 2023), which SSMs areexplicitly designed to address via their close architectural similarity torecurrent neural networks (RNNs). But do SSMs truly have an advantage (overtransformers) in expressive power for state tracking? Surprisingly, the answeris no. Our analysis reveals that the expressive power of SSMs is limited verysimilarly to transformers: SSMs cannot express computation outside thecomplexity class $\mathsf{TC}^0$. In particular, this means they cannot solvesimple state-tracking problems like permutation composition. It follows thatSSMs are provably unable to accurately track chess moves with certain notation,evaluate code, or track entities in a long narrative. To supplement our formalanalysis, we report experiments showing that Mamba-style SSMs indeed strugglewith state tracking. Thus, despite its recurrent formulation, the "state" in anSSM is an illusion: SSMs have similar expressiveness limitations tonon-recurrent models like transformers, which may fundamentally limit theirability to solve real-world state-tracking problems.

    Translation (by gpt-3.5-turbo)

• 状態空間モデル（SSM）は、以前には普及していたトランスフォーマーアーキテクチャと比較して、大規模言語モデル（LLM）を構築するための潜在的な代替アーキテクチャとして登場しています。トランスフォーマーの理論上の弱点の1つは、特定の種類の順次計算や状態追跡を表現できないという点です（Merrill＆Sabharwal、2023年）。これに対して、SSMは再帰ニューラルネットワーク（RNN）との密接なアーキテクチャの類似性によって、明示的に対処するように設計されています。しかし、SSMが状態追跡の表現力で本当に（トランスフォーマーよりも）優位性を持っているのでしょうか？驚くべきことに、その答えは「いいえ」です。私たちの分析によると、SSMの表現力は、トランスフォーマーと非常に類似して制限されています：SSMは複雑性クラス$\mathsf{TC}^0$の外での計算を表現することができません。特に、これは、置換合成のような単純な状態追跡問題を解決することができないことを意味します。これにより、SSMは、特定の表記法でチェスの手を正確に追跡したり、コードを評価したり、長い物語の中のエンティティを追跡することが証明上できないことが明らかになります。形式的な分析を補完するために、MambaスタイルのSSMが実際に状態追跡に苦労していることを示す実験を報告しています。したがって、再帰的な構成にもかかわらず、SSMの「状態」は幻想です：SSMは、トランスフォーマーのような非再帰モデルと同様の表現力の制限を持っており、これが基本的に実世界の状態追跡問題を解決する能力を制限する可能性があります。

  Summary (by gpt-3.5-turbo)

• SSM（状態空間モデル）は、トランスフォーマーよりも優れた状態追跡の表現力を持つと期待されていましたが、実際にはその表現力は制限されており、トランスフォーマーと類似しています。SSMは複雑性クラス$\mathsf{TC}^0$の外での計算を表現できず、単純な状態追跡問題を解決することができません。このため、SSMは実世界の状態追跡問題を解決する能力に制限がある可能性があります。

[AkihikoWatanabe]

しかし、SSMが状態追跡の表現力で本当に（トランスフォーマーよりも）優位性を持っているのでしょうか？驚くべきことに、その答えは「いいえ」です。私たちの分析によると、SSMの表現力は、トランスフォーマーと非常に類似して制限されています：SSMは複雑性クラス$\mathsf{TC}^0$の外での計算を表現することができません。特に、これは、置換合成のような単純な状態追跡問題を解決することができないことを意味します。これにより、SSMは、特定の表記法でチェスの手を正確に追跡したり、コードを評価したり、長い物語の中のエンティティを追跡することが証明上できないことが明らかになります。

なん…だと…