# Sequential-Parallel Duality in Prefix Scannable Models

arXiv: https://arxiv.org/abs/2506.10918 · HTML: https://mlsanity.com/paper/2506.10918/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Core SSM architectures for language, one of 10 directions in State-space sequence models (S4, Mamba).
- Builds on 43 of its 57 references that are in the map.
- First posted on arXiv 12 Jun 2025.

## Placed in

- State-space sequence models (S4, Mamba) / [Core SSM architectures for language](https://mlsanity.com/ssm/core-ssm-architectures-for-language/)

## Builds on (most cited first, 30 of 43)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [WaveNet: A Generative Model for Raw Audio](https://mlsanity.com/paper/1609.03499/) (2016)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality](https://mlsanity.com/paper/2405.21060/) (2024)
- [Language Modeling with Gated Convolutional Networks](https://mlsanity.com/paper/1612.08083/) (2016)
- [Retentive Network: A Successor to Transformer for Large Language Models](https://mlsanity.com/paper/2307.08621/) (2023)
- [Convolutional Sequence to Sequence Learning](https://mlsanity.com/paper/1705.03122/) (2017)
- [Gated Delta Networks: Improving Mamba2 with Delta Rule](https://mlsanity.com/paper/2412.06464/) (2024)
- [Gated Linear Attention Transformers with Hardware-Efficient Training](https://mlsanity.com/paper/2312.06635/) (2023)
- [Linear Transformers Are Secretly Fast Weight Programmers](https://mlsanity.com/paper/2102.11174/) (2021)
- [Parallelizing Linear Transformers with the Delta Rule over Sequence Length](https://mlsanity.com/paper/2406.06484/) (2024)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [xLSTM: Extended Long Short-Term Memory](https://mlsanity.com/paper/2405.04517/) (2024)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Simple linear attention language models balance the recall-throughput tradeoff](https://mlsanity.com/paper/2402.18668/) (2024)
- [Zoology: Measuring and Improving Recall in Efficient Language Models](https://mlsanity.com/paper/2312.04927/) (2023)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [Independently Recurrent Neural Network (IndRNN): Building A Longer and Deeper RNN](https://mlsanity.com/paper/1803.04831/) (2018)
- [RWKV-7 "Goose" with Expressive Dynamic State Evolution](https://mlsanity.com/paper/2503.14456/) (2025)
- [Parallelizing Linear Recurrent Neural Nets Over Sequence Length](https://mlsanity.com/paper/1709.04057/) (2017)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Hierarchically Gated Recurrent Neural Network for Sequence Modeling](https://mlsanity.com/paper/2311.04823/) (2023)

## Built on by (most cited first, 8 of 8)

- [Kimi Linear: An Expressive, Efficient Attention Architecture](https://mlsanity.com/paper/2510.26692/) (2025)
- [Dynamic Chunking for End-to-End Hierarchical Sequence Modeling](https://mlsanity.com/paper/2507.07955/) (2025)
- [In-Place Test-Time Training](https://mlsanity.com/paper/2604.06169/) (2026)
- [Fast weight programming and linear transformers: from machine learning to neurobiology](https://mlsanity.com/paper/2508.08435/) (2025)
- [Pretraining Recurrent Networks without Recurrence](https://mlsanity.com/paper/2606.06479/) (2026)
- [Recurrence-Complete Frame-based Action Models](https://mlsanity.com/paper/2510.06828/) (2025)
- [Length Generalization with Log-Depth Recurrent Units](https://mlsanity.com/paper/2605.26035/) (2026)
- [SMat-Attention: Structured Long-Context Sequence Modeling](https://mlsanity.com/paper/2609.36062/) (2026)

## Abstract (arXiv)

Modern neural sequence models are designed to meet the dual mandate of parallelizable training and fast sequential inference. Recent developments have given rise to various models, such as Gated Linear Attention (GLA) and Mamba, that achieve such ``sequential-parallel duality.'' This raises a natural question: can we characterize the full class of neural sequence models that support near-constant-time parallel evaluation and linear-time, constant-space sequential inference? We begin by describing a broad class of such models -- state space models -- as those whose state updates can be computed using the classic parallel prefix scan algorithm with a custom associative aggregation operator. We then define a more general class, Prefix-Scannable Models (PSMs), by relaxing the state aggregation operator to allow arbitrary (potentially non-associative) functions such as softmax attention. This generalization unifies many existing architectures, including element-wise RNNs (e.g., Mamba) and linear transformers (e.g., GLA, Mamba2, mLSTM), while also introducing new models with softmax-like operators that achieve O(1) amortized compute per token and log(N) memory for sequence length N. We empirically evaluate such models on illustrative small-scale language modeling and canonical synthetic tasks, including state tracking and associative recall. Empirically, we find that PSMs retain the expressivity of transformer-based architectures while matching the inference efficiency of state space models -- in some cases exhibiting better length generalization than either.