Expressivity-Efficiency Tradeoffs for Hybrid Sequence Models

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 \times$ as many parameters. We additionally demonstrate that hybrid models exhibit stronger length generalization and out-of-distribution robustness than non-hybrids.

Modern AI systems are becoming increasingly powerful, but many of today’s models become slower as conversations or documents grow longer. Researchers have recently proposed new types of model components that avoid this slowdown, though these systems are often less flexible than standard approaches. In this work, we study hybrid models that combine both kinds of components: one that is highly expressive but computationally costly, and another that is more efficient. In practice, these hybrid models have already shown strong performance, but it has remained unclear why they work so well. We provide both theoretical and experimental evidence that hybrid models can achieve capabilities that neither type of model can match efficiently on its own. We identify a family of tasks where pure models require substantially more memory or parameters, while hybrid models can solve the same problems compactly and efficiently. We then confirm these findings experimentally by training different model types on representative tasks from this family. At comparable sizes, the hybrid models succeed while the pure models often fail. We also show that hybrids generalize better to longer inputs and remain more reliable when tested in settings different from those seen during training.