論文の概要: The Computational Complexity of Satisfiability in State Space Models

• arxiv url: http://arxiv.org/abs/2508.18162v1
• Date: Mon, 25 Aug 2025 16:12:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-26 18:43:45.854717
• Title: The Computational Complexity of Satisfiability in State Space Models
• Title（参考訳）: 状態空間モデルにおける満足度の計算複雑性
• Authors: Eric Alsmann, Martin Lange,
• Abstract要約: ssmSATは一般には決定不可能であり、SSMの計算能力を反映している。 実際の設定により、ssmSATが決定可能な2つの自然的制約を識別する。
• 参考スコア（独自算出の注目度）: 4.5835414225547195
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We analyse the complexity of the satisfiability problem ssmSAT for State Space Models (SSM), which asks whether an input sequence can lead the model to an accepting configuration. We find that ssmSAT is undecidable in general, reflecting the computational power of SSM. Motivated by practical settings, we identify two natural restrictions under which ssmSAT becomes decidable and establish corresponding complexity bounds. First, for SSM with bounded context length, ssmSAT is NP-complete when the input length is given in unary and in NEXPTIME (and PSPACE-hard) when the input length is given in binary. Second, for quantised SSM operating over fixed-width arithmetic, ssmSAT is PSPACE-complete resp. in EXPSPACE depending on the bit-width encoding. While these results hold for diagonal gated SSM we also establish complexity bounds for time-invariant SSM. Our results establish a first complexity landscape for formal reasoning in SSM and highlight fundamental limits and opportunities for the verification of SSM-based language models.
• Abstract（参考訳）: 本研究では、状態空間モデル(SSM)に対する満足度問題ssmSATの複雑さを分析し、入力シーケンスがモデルを受け入れ設定に導くことができるかどうかを問う。 ssmSATは一般には決定不可能であり、SSMの計算能力を反映している。 実際の設定により、ssmSATが決定可能となり、対応する複雑性境界を確立するための2つの自然的制約を同定する。 まず、コンテキスト境界長を持つSSMの場合、ssmSATは、入力長が一意的に与えられるとき、および入力長が二項で与えられるとき、NEXPTIME(およびPSPACE-hard)においてNP完全である。 第二に、固定幅演算を演算する量子化SSMでは、ssmSATはPSPACE完全respである。 EXPSPACEではビット幅のエンコーディングに依存する。 これらの結果は対角ゲート付きSSMに対して成り立つが、時間不変SSMの複雑性境界も確立する。 本研究は,SSMにおける形式的推論のための最初の複雑性ランドスケープを確立し,SSMに基づく言語モデルを検証するための基本的限界と機会を強調した。

関連論文リスト

• Overcoming Long-Context Limitations of State-Space Models via Context-Dependent Sparse Attention [17.498728107106817]
  状態空間モデル(SSM)の長期コンテキストモデリング機能の解析と改善に焦点をあてる。 本稿では,広く使用されている合成課題である連想的リコールが,実世界の長文モデリングの複雑さを十分に表していることを示す。 理論的解析と実世界の応用のギャップを埋めるために, 疎鍵選択による局所性に敏感なハッシュ注意を提案する。
  論文  参考訳（メタデータ） (2025-07-01T06:03:50Z)
• Sequential-Parallel Duality in Prefix Scannable Models [68.39855814099997]
  近年では Gated Linear Attention (GLA) や Mamba など様々なモデルが開発されている。 ニアコンスタント時間並列評価と線形時間、定数空間シーケンシャル推論をサポートするニューラルネットワークモデルの全クラスを特徴付けることができるだろうか?
  論文  参考訳（メタデータ） (2025-06-12T17:32:02Z)
• SparseSSM: Efficient Selective Structured State Space Models Can Be Pruned in One-Shot [8.080568103779893]
  Mambaのような状態空間言語モデルは、線形複雑性推論を許容しながらTransformerの品質にマッチする。 既存のワンショットプルーニング手法はアテンションブロックに適合し、時間共有および離散化された状態遷移行列を考慮できない。 SparseSSMは、古典的最適な脳外科医(OBS)フレームワークをステートスペースアーキテクチャに拡張した最初のトレーニングフリープルーニングフレームワークである。
  論文  参考訳（メタデータ） (2025-06-11T11:14:57Z)
• Understanding and Mitigating Bottlenecks of State Space Models through the Lens of Recency and Over-smoothing [56.66469232740998]
  構造化状態空間モデル (Structured State Space Models, SSMs) は, 強い相対バイアスによって本質的に制限されていることを示す。 このバイアスにより、モデルが遠方の情報を思い出す能力が損なわれ、堅牢性の問題がもたらされる。 本研究では, 状態遷移行列の2つのチャネルをSSMで分極し, それぞれ0と1に設定し, 電流バイアスと過平滑化に同時に対処することを提案する。
  論文  参考訳（メタデータ） (2024-12-31T22:06:39Z)
• On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages [56.22289522687125]
  SSM(Selective State-space Model)はTransformerの代替品である。 正規言語タスクにおける表現性や長さの一般化性能を解析する。 本稿では,Selective Dense State-Space Model (SD-SSM)を紹介する。
  論文  参考訳（メタデータ） (2024-12-26T20:53:04Z)
• Provable Benefits of Complex Parameterizations for Structured State Space Models [51.90574950170374]
  構造化状態空間モデル (Structured State Space Model, SSM) は、指定された構造に固執する線形力学系である。 パラメータ化が現実の典型的なニューラルネットワークモジュールとは対照的に、SSMは複雑なパラメータ化を使用することが多い。 本稿では,実対角 SSM と複素対角 SSM の形式的ギャップを確立することにより,SSM の複雑なパラメータ化の利点を説明する。
  論文  参考訳（メタデータ） (2024-10-17T22:35:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。