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:
- The Expressivity Gap: They consistently underperform Transformers on language modeling tasks, often by multiple points in perplexity.
- 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.
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.
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