To Infinity and Beyond: Tool-Use Unlocks Length Generalization in State Space Models
This addresses the efficiency and generalization challenges of SSMs for long-context applications, offering a potential alternative to Transformers in interactive and agentic settings.
The paper demonstrates that State Space Models (SSMs) inherently fail at long-form generation tasks but can overcome this limitation by using external tools, enabling them to solve tractable problems and generalize to arbitrary lengths across arithmetic, reasoning, and coding tasks.
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.