Expressivity-Efficiency Tradeoffs for Hybrid Sequence Models
John Cooper, Ilias Diakonikolas, Mingchen Ma, Frederic Sala · 2026
Read Expressivity-Efficiency Tradeoffs for Hybrid Sequence Models by John Cooper, Ilias Diakonikolas, Mingchen Ma, Frederic Sala (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-08859.txt.
Introduction
John Cooper and colleagues probe where hybrid sequence models beat their pure parents. Pure attention or state-space models need either many parameters or much working memory on a broad task family. Small hybrids provably solve selective copying and associative recall, and learned hybrids beat pure models with up to six times the parameters while generalizing better in length and distribution.
Catalog record
| CREATOR | John Cooper, Ilias Diakonikolas, Mingchen Ma, Frederic Sala |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95675 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.08859
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Expressivity-Efficiency Tradeoffs for Hybrid Sequence Models John Cooper, Ilias Diakonikolas, Mingchen Ma, Frederic Sala Abstract Hybrid sequence models—combining Transformer and state-space model layers—seek to gain the expressive versatility of attention as well as the computational efficiency of state-space model layers. Despite burgeoning interest in hybrid models, we lack a basic understanding of the settings where—and underlying mechanisms through which—they offer benefits over their constituent models. In this paper, we study this question, focusing on a broad family of core synthetic tasks. For this family of tasks, we prove the existence of fundamental limitations for non-hybrid models. Specifically, any Transformer or state-space model that solves the underlying task requires either a large number of parameters or a large working memory. On the other hand, for two prototypical tasks within this family—namely selective copying and associative recall—we construct hybrid models of small size and working memory that provably solve these tasks, thus achieving the best of both worlds. Our experimental evaluation empirically validates our theoretical findings. Importantly, going beyond the settings in our theoretical analysis, we empirically show that learned—rather than constructed—hybrids outperform non-hybrid models with up to 6 × 6\times as many parameters. We additionally demonstrate that hybrid models exhibit stronger length generalization and out-of-distribution robustness than non-hybrids. 1 1 1 Code is available in this link . * denotes equal contribution. 1 Introduction Transformers are the workhorse architecture for modern language models. While highly expressive and capable, Transformer-based models suffer from high complexity, particularly for inference time processing of long sequence inputs. As a result, developing alternative non-Transformer architectures has become among the most important problems in LLM development. Structured state space models (SSMs) like Mamba 10 are among the most promising such alternatives. Such models trade off complexity for expressivity 14 , achieving higher throughput—but typically lower performance—compared to Transformer-based models. A natural question is whether we can sidestep this tradeoff and produce a model architecture that offers the best of both worlds. Hybrid sequence models seek to achieve this objective. These models, which mix layers from Transformer architectures (e.g., attention layers) with SSM layers, ideally outperform either Transformer-only or SSM-only models. In a short time, hybrids that can empirically do so on particular tasks have been scaled up from tiny sizes to as large as 50 billion parameters. For example, Nvidia’s Nemotron-H hybrid model family 3 offers both better downstream evaluation performance and higher throughput (due to the presence of lower-complexity Mamba layers) than Transformer-only baselines. Despite these empirical successes, we have no principled understanding of why hybrid models can outperform models made up of a single type of layer. Similarly, we do not yet know for what basic tasks we should expect hybrids to behave in this way. This paper takes the first steps towards providing a fundamental theory addressing architectural tradeoffs for hybrid models . It does so by first showing that on a family of core tasks where pure (i.e., standard Transformer-only and SSM-only) models provably suffer from limitations (in terms complexity and memory). In contrast, we build constructions of hybrid models that do not have the same limitations on representative tasks—including key tasks like associative recall and selective copying—thus exhibiting provable benefits for hybrids. Concretely, we evaluate the performance of a model by analyzing its input-independent memory (model size) and input-dependent memory (working memory) . We focus on a function-composition family of tasks (Fig. 1 ) that combine both a long-context control variable and a local context-addressable lookup; such tasks naturally model real-world data. For these, (i) under an injectivity condition, we prove that, for this family, any pure SSM requires large internal state (or many layers); as a result, their size scales linearly with respect to the hidden dimension of the problem to solve the problem. Likewise, (ii), under a local-sensitivity condition, any sliding-window Transformer (which includes full-window attention) requires a large window scaling linearly with respect to the length of the input context. Together, this pair of results indicates that for a broad class of tasks, pure SSM-based models and pure Transformer-based models fail to achieve good expressivity and inference efficiency simultaneously . We study two representative synthetic tasks in this family, namely selective copying and a variant of associative recall 1 . For these tasks, we construct provably successful shallow hybrid models whose size scales with the logarithm of the size of the tasks while using only sublinear memory. Empirically, we validate our theoretical results and investigate hybrid versus non-hybrid performance in further settings and on additional tasks, such multi-key associative recall (MKAR) and needle-in-a-haystack (NH). We find that for selective copying and MKAR, hybrids can perform the task with similar or better quality than the pure models with 6 times fewer parameters . For associative recall with decoding, at the tested scales, the pure models never match the performance possible with the hybrid model. On top of measuring performance at fixed model sizes, we observe that hybrid models exhibit stronger length generalization and out-of-distribution (OOD) robustness. We see that when trained on the same distribution of short examples, hybrids consistently out-perform pure Transformers by around 10% accuracy for long sequences. For out-of-distribution testing, the hybrid model sometimes attains over 15% higher performance than either the Transformer or the SSM with around the same number of parameters. Roadmap of the paper. In Section 2 , we provide necessary preliminaries and notations. In Section 3 , we introduce a family of tasks formulated as computing a function composition and provide conditions under which non-hybrid models fail to solve the tasks efficiently. Next, in Section 4 , we focus on two specific tasks (of varying difficulty) that are within this family and construct hybrid models that outperform non-hybrids. In Section 5 , we conduct experiments to show the benefits of hybrid models empirically. Figure 1 : Example function composition task. The answer to a learned question only depends on a part of the long context input. 2 Preliminaries and Notations We provide necessary preliminaries and notation. A complete list of preliminaries is deferred to Appendix B . We consider sequence-to-sequence token prediction problems. Let \mathcal{V} be some vocabulary of tokens, V=|\mathcal{V}| , and \vec{\mathbf{x}}=(\mathbf{x}_{i})_{i=1}^{L} be an input sequence. A language model M a is sequence-to-sequence map M:\mathcal{V}^{L}\to\mathcal{V}^{m} of the form M(\vec{\mathbf{x}})=F_{N}\circ F_{N-1}\circ\dots\circ F_{1}(\vec{\mathbf{x}}) , where \circ is function composition and each F_{i} is a sequence-to-sequence map called a layer . We will consider types of layers. Transformer Layer. Consider an embedded input sequence \vec{\mathbf{x}}=(\mathbf{x}_{1},\dots,\mathbf{x}_{L}) such that \mathbf{x}_{i}\in\mathbb{R}^{d} . An attention head \mathrm{Attn} is defined by matrices \mathbf{W}_{k},\mathbf{W}_{q},\mathbf{W}_{v}\in\mathbb{R}^{d\times d} such that \mathrm{Attn}(\vec{\mathbf{x}})_{j}=\sum_{i=1}^{n}\alpha_{ji}\mathbf{W}_{v}\mathbf{x}_{i} , where \displaystyle\alpha_{ji}:=\frac{\exp\left((\mathbf{W}_{q}\mathbf{x}_{j})\cdot(\mathbf{W}_{k}\mathbf{x}_{i})\right)}{\sum_{i=1}^{n}\exp\left((\mathbf{W}_{q}\mathbf{x}_{j})\cdot(\mathbf{W}_{k}\mathbf{x}_{i})\right)}. An attention layer \mathrm{AT} is defined by H attention heads \mathrm{Attn}_{1},\dots,\mathrm{Attn}_{H} and a projection matrix \mathbf{W}_{o}\in\mathbb{R}^{d\times dH} . Denote by \mathbf{O}:=(\mathrm{Attn}_{1}(\vec{\mathbf{x}})^{\top},\dots,\mathrm{Attn}_{H}(\vec{\mathbf{x}})^{\top})^{\top}\in\mathbb{R}^{dH\times L} the concatenation of the outputs of the H attention heads, so the attention layer \mathrm{AT}(\vec{\mathbf{x}}) outputs \mathbf{W}_{o}\mathbf{O}\in\mathbb{R}^{d\times L} . A Transformer layer \mathrm{TF} is defined by an attention layer \mathrm{AT} and an MLP layer. In particular, an MLP layer is defined as f(\mathbf{x}):\mathbb{R}^{d}\to\mathbb{R}^{d} as f(\mathbf{x})=\mathbf{U}_{2}\sigma(\mathbf{U}_{1}\mathbf{x}) , where \mathbf{U}_{1},\mathbf{U}_{2} are matrices and \sigma is an activation function applied coordinate-wise. Specifically, \mathrm{TF}(\vec{\mathbf{x}})=\mathrm{MLP}(\mathrm{AT}(\vec{\mathbf{x}})) . State-Space Model Layer. We use a similar formalism of a SSM layer as in 14 . A state space \mathcal{S} is a finite set. We denote