Hungry Hungry Hippos: Towards Language Modeling with State Space Models

Daniel Y. Fu, Tri Dao, Khaled K. Saab, Armin W. Thomas, Atri Rudra, Christopher Ré

TL;DR

State Space Models (SSMs) offer efficient linear scaling for long sequences but have historically lagged behind Transformers in language modeling quality and hardware efficiency. This paper introduces H3, a novel SSM layer that closes the expressivity gap by explicitly enabling token recall and comparison, alongside FlashConv, a hardware-aware algorithm that accelerates training and enables 2.4× faster text generation than Transformers.

What Problem Does This Paper Address?

While Transformers dominate modern natural language processing, their core mechanism—self-attention—suffers from a fundamental flaw: it scales quadratically ($O(N^2)$) with sequence length. This makes processing long documents or extended conversations prohibitively expensive.

Structured State Space Models (SSMs) have emerged as a promising alternative because they scale nearly linearly ($O(N \log N)$) with sequence length. However, SSMs have historically faced two major roadblocks:

  1. The Expressivity Gap: They consistently underperform Transformers on language modeling tasks, often by multiple points in perplexity.
  2. The Hardware Barrier: Despite their theoretical efficiency, SSMs are slow in practice on modern GPUs because standard convolution operations are memory-bound and fail to utilize specialized hardware like Tensor Cores.

This paper aims to understand and close this expressivity gap while designing hardware-aware algorithms to make SSMs faster than attention in practice.

Methods

The authors introduce two core innovations to solve the expressivity and hardware utilization problems:

1. The H3 (Hungry Hungry Hippo) Layer

To understand why SSMs struggle with text, the authors analyzed synthetic language tasks. They found that standard SSMs fail at two key capabilities: recalling past tokens and comparing tokens across a sequence.

To fix this, the H3 layer stacks two discrete SSMs with multiplicative gating interactions, loosely inspired by linear attention:

  • Shift SSM: Acts like a shift register to maintain a local memory of recent tokens.
  • Diagonal SSM: Maintains a long-term log of tokens over the entire sequence.

By multiplying the outputs of these SSMs with input projections (analogous to Queries, Keys, and Values), H3 allows the model to explicitly compare tokens across the sequence and recall them when necessary.

2. FlashConv

To overcome the hardware barrier, the authors developed FlashConv, a hierarchical algorithm designed to optimize FFT-based convolutions on modern GPU architectures:

  • Fused Block FFT: For sequences up to 8K, FlashConv fuses the FFT, pointwise multiplication, and inverse FFT into a single kernel to minimize slow GPU memory reads/writes. It restructures the FFT into a series of matrix multiplications, allowing the algorithm to exploit fast GPU Tensor Cores.
  • State-Passing Algorithm: For sequences longer than 8K that cannot fit entirely into GPU SRAM, FlashConv splits the input into chunks, computes the block FFT per chunk, and uses the recurrent property of SSMs to pass the boundary states exactly to the next chunk.
Figure 1: Left: H3 stacks two discrete SSMs with shift and diagonal matrices and uses multiplicative interactions between input projections and their outputs to model comparisons between points in a sequence. Middle: H3 can perform associative recall—which is easy for attention, but not existing SSMs. Right: FlashConv uses a new state-passing algorithm over fused block FFTConv to increase hardware efficiency of SSMs, allowing H3 to scale to billion-parameter models.

Datasets

The models were trained and evaluated across a diverse set of benchmarks:

  • Synthetic Tasks: Induction Head and Associative Recall.
  • Language Modeling: OpenWebText, The Pile (used to scale hybrid models up to 2.7B parameters), WikiText-103, and PG-19.
  • Downstream NLU: The SuperGLUE benchmark (including tasks like WSC, WIC, RTE, CB, MultiRC, ReCoRD, BoolQ, and COPA).
  • Long-Range Modeling: Long Range Arena (LRA).
  • Non-Text Modalities: SC10 (raw speech commands), TUSZ v1.5.2 (EEG seizure classification), and human fMRI brain dynamics datasets (HCP and MDTB).

Key Insights and Ideas

  • The Expressivity Gap is Mechanistic: The reason SSMs couldn't model language well wasn't a vague lack of capacity; it was a specific inability to perform associative recall (e.g., remembering that the value "3" follows the key "a"). Adding explicit QKV-style multiplicative gating solves this.
  • Attention is Only Needed Sparsely: You don't need to completely eliminate attention to get the benefits of linear scaling. Replacing all but two attention layers with H3 layers creates a hybrid model that actually outperforms pure Transformers.
  • Defeating the Hardware Lottery: Algorithms succeed not just based on FLOP counts, but on how well they match hardware design. By turning the traditionally memory-bound FFT into block matrix multiplications, FlashConv allows SSMs to finally leverage the massive matrix-multiply power of modern GPUs.

Key Results

Language Modeling Quality

Hybrid H3-attention models consistently outperform standard Transformers across multiple datasets. At the 125M parameter scale on OpenWebText, the hybrid model beats Transformers by 1.0 perplexity point. When scaled up to 2.7B parameters on the Pile, the hybrid H3 model achieves lower perplexity than equivalent GPT-Neo and OPT baselines.

Perplexity comparison of H3 variants against Transformers across the Pile, OpenWebText, and WikiText103.

Downstream and Long-Context Performance

  • SuperGLUE: Hybrid H3 models match or exceed Transformer baselines on a majority of NLU tasks in zero- and few-shot settings.
  • Speedups: FlashConv accelerates the S4 state-space model by 2× on the Long Range Arena benchmark.
  • Inference Throughput: Because the SSM layers can be written in a recurrent form during generation, the hybrid H3 model generates text 2.4× faster than a standard Transformer during inference.

Limitations and Future Work

  • Pure H3 Generation Struggles: While hybrid models (H3 + 2 attention layers) perform exceptionally well, pure H3 models still struggle on zero-shot generation tasks, often generating long, irrelevant text responses because they fail to grasp formatting without few-shot examples.
  • Borrowed Hyperparameters: All large-scale H3 models were trained using standard GPT-3 hyperparameters. The authors note that optimizing hyperparameters specifically for SSM architectures could unlock even better performance.
  • Architectural Exploration: The H3 layer represents a simple combination of two SSMs; exploring more sophisticated combinations of state-space models and attention remains a highly promising frontier.

Summary updated

Abstract

State space models (SSMs) have demonstrated state-of-the-art sequence modeling performance in some modalities, but underperform attention in language modeling. Moreover, despite scaling nearly linearly in sequence length instead of quadratically, SSMs are still slower than Transformers due to poor hardware utilization. In this paper, we make progress on understanding the expressivity gap between SSMs and attention in language modeling, and on reducing the hardware barrier between SSMs and attention. First, we use synthetic language modeling tasks to understand the gap between SSMs and attention. We find that existing SSMs struggle with two capabilities: recalling earlier tokens in the sequence and comparing tokens across the sequence. To understand the impact on language modeling, we propose a new SSM layer, H3, that is explicitly designed for these abilities. H3 matches attention on the synthetic languages and comes within 0.4 PPL of Transformers on OpenWebText. Furthermore, a hybrid 125M-parameter H3-attention model that retains two attention layers surprisingly outperforms Transformers on OpenWebText by 1.0 PPL. Next, to improve the efficiency of training SSMs on modern hardware, we propose FlashConv. FlashConv uses a fused block FFT algorithm to improve efficiency on sequences up to 8K, and introduces a novel state passing algorithm that exploits the recurrent properties of SSMs to scale to longer sequences. FlashConv yields 2$\times$ speedup on the long-range arena benchmark and allows hybrid language models to generate text 2.4$\times$ faster than Transformers. Using FlashConv, we scale hybrid H3-attention language models up to 2.7B parameters on the Pile and find promising initial results, achieving lower perplexity than Transformers and outperforming Transformers in zero- and few-shot learning on a majority of tasks in the SuperGLUE benchmark.
BibTeX
@inproceedings{fu2023hungry,
  author = {Daniel Y. Fu and Tri Dao and Khaled K. Saab and Armin W. Thomas and Atri Rudra and Christopher Ré},
  title = {{Hungry Hungry Hippos: Towards Language Modeling with State Space Models}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=COZDy0WYGg},
}
Figure