On Structured State-Space Duality

Structured State-Space Duality (SSD) [Dao \& Gu, ICML 2024] is an equivalence between a simple Structured State-Space Model (SSM) and a masked attention mechanism. In particular, a state-space model with a scalar-times-identity state matrix is equivalent to a masked self-attention with a $1$-semiseparable causal mask. Consequently, the same sequence transformation (model) has two algorithmic realizations: as a linear-time $O(T)$ recurrence or as a quadratic-time $O(T^2)$ attention. In this note, we formalize and generalize this duality: (i) we extend SSD from the scalar‑identity case to general diagonal SSMs (diagonal state matrices); (ii) we show that these diagonal SSMs match the scalar case's training complexity lower bounds while supporting richer dynamics; (iii) we establish a necessary and sufficient condition under which an SSM is equivalent to $1$-semiseparable masked attention; and (iv) we show that such duality fails to extend to standard softmax attention due to rank explosion. Together, these results tighten the bridge between recurrent SSMs and Transformers, and widen the design space for expressive yet efficient sequence models. Code is available at https://github.com/MAGICS-LAB/state_space_daulity.

Modern AI models often process sequences, such as text, audio, and time series. Two common designs do this in different ways. Recurrent models carry a small memory from one step to the next. Attention models compare positions across a sequence. The first design is efficient. The second design is expressive, but often more costly. This paper studies when these two designs compute the same rule. We extend a known equivalence from a simple state-space model to a richer diagonal state-space model. This richer model can track several time scales at once. It also keeps the same main efficiency as the simpler model. We further give an exact condition for when a recurrent model has a masked-attention form. We also show a sharp limit. Standard softmax attention usually cannot be rewritten exactly as a finite recurrent model. These results clarify the relation between state-space models and attention. They also suggest how to design sequence models that are both expressive and efficient.