2025-11-16T06:22:12.451775

To Infinity and Beyond: Tool-Use Unlocks Length Generalization in State Space Models

Malach, Saremi, Williamson et al.

State Space Models (SSMs) have become the leading alternative to Transformers for sequence modeling. Their primary advantage is efficiency in long-context and long-form generation, enabled by fixed-size memory and linear scaling of computational complexity. We begin this work by showing a simple theoretical result stating that SSMs cannot accurately solve any ``truly long-form'' generation problem (in a sense we formally define), undermining their main competitive advantage. However, we show that this limitation can be mitigated by allowing SSMs interactive access to external tools. In fact, we show that given the right choice of tool access and problem-dependent training data, SSMs can learn to solve any tractable problem and generalize to arbitrary problem length/complexity (i.e., achieve length generalization). Following our theoretical finding, we demonstrate that tool-augmented SSMs achieve remarkable length generalization on a variety of arithmetic, reasoning, and coding tasks. These findings highlight SSMs as a potential efficient alternative to Transformers in interactive tool-based and agentic settings.

academic

無限へと: ツール使用が状態空間モデルの長さ汎化を解き放つ

基本情報

論文ID: 2510.14826
タイトル: To Infinity and Beyond: Tool-Use Unlocks Length Generalization in State Space Models
著者: Eran Malach, Omid Saremi, Sinead Williamson, Arwen Bradley, Aryo Lotfi, Emmanuel Abbe, Josh Susskind, Etai Littwin
機関: Apple
分類: cs.LG
発表日: 2025年10月17日
論文リンク: https://arxiv.org/abs/2510.14826

要約

状態空間モデル(SSM)は、シーケンスモデリングにおけるTransformerの主要な代替案として台頭しており、固定サイズのメモリと線形計算複雑度を通じて長コンテキストと長シーケンス生成の効率性を実現することが主な利点である。本論文は、SSMが正式に定義された意味での「真の長シーケンス」生成問題を正確に解決できないことを証明する単純な理論的結果を最初に提示し、その主要な競争上の利点を弱める。しかし、この制限はSSMに対話的な外部ツールアクセスを提供することで緩和できることが示されている。実際、ツールアクセスと問題関連の訓練データの適切な選択の下では、SSMは任意の問題の長さ/複雑度に汎化して任意の処理可能な問題を解決することを学習できる。理論的発見に基づいて、著者らは、ツール強化されたSSMが様々な算術、推論、およびプログラミングタスクにおいて顕著な長さ汎化能力を実現することを実証している。

研究背景と動機

問題背景

Transformerの計算ボトルネック: Transformerは注意機構のため、計算複雑度はシーケンス長に対して二次的に増加し、メモリは長さに対して線形に増加する。これは長コンテキストと長シーケンス生成タスクにおいて主要な制限となる。
SSMの台頭: この問題を解決するため、研究者らは線形Transformerや状態空間モデル(SSM)を含む様々な代替アーキテクチャを提案した。Mamba、DeltaNetなどがこれに該当し、これらのアーキテクチャは固定メモリと線形計算複雑度を実現している。
SSMの制限: SSMは効率性において利点を持つにもかかわらず、長シーケンスメモリとコンテキスト学習を必要とするタスクにおいて顕著な制限が存在することが指摘されている。

研究動機

著者らは、特に出力長が問題複雑度とともに増加するタスクにおいて、長シーケンス生成タスクにおけるSSMの能力と制限を理解することを目指している。これらはSSMがTransformerと比較して明らかな推論効率の利点を示すタスクの種類である。

核心的貢献

理論的負の結果: SSMが「真の長シーケンス生成問題」を解決できないことを証明した。これは任意の長さの思考の連鎖(CoT)生成を許可する場合でも成立する。
ツール使用の理論的枠組み: ReActエージェントを研究するための新しい理論的枠組みを導入し、対話的なツール使用がSSMの能力を大幅に強化できることを証明した。
長さ汎化の充分性定理: 適切なツールアクセスと特定の訓練データを備えたSSMが、任意の処理可能な長シーケンス生成タスクにおいて長さ汎化を実現できることを証明した。
実験的検証: 算術、論理推論、およびプログラミングタスクにおいて、ツール強化SSMの優れた長さ汎化能力を実証した。