State Space Duality (SSD) & Hybrid Mamba-2: Sub-Quadratic Sequence Parallelism
In Attention Engineering: From MHA to GQA, MLA & FlashAttention, we saw how IO-aware tiling eliminates $O(T^2)$ HBM materialization during training, yet autoregressive decoding remains fundamentally bottlenecked by a KV-cache that grows linearly with sequence length $T$. Conversely, selective State Space Models (Mamba-1; Gu & Dao, 2023) compress history into a fixed-size recurrent state $h_t \in \mathbb{R}^{N \times P}$, achieving $O(1)$ inference memory per step – but relied on custom associative parallel scans that could not leverage GPU Tensor Cores (MMA instructions).
Structured State Space Duality (SSD / Mamba-2) (Dao & Gu, 2024, arXiv:2405.21060; GitHub) proves that selective state spaces and masked linear attention are exact dual views of the same $1$-semiseparable matrix transformation $Y = M X$. By partitioning sequences into chunks of length $Q$ and reformulating intra-chunk recurrence as dense GEMMs alongside inter-chunk state passing, Mamba-2 runs $2\text{–}8\times$ faster on Tensor Cores while pairing seamlessly with Ring Attention (Liu et al., arXiv:2310.01889) in hybrid long-context architectures.
0. The State Space Duality (SSD) Theorem: Linear Recurrence $\equiv$ Semiseparable Attention
Consider a selective time-varying linear recurrence over input projections $x_t \in \mathbb{R}^P$, state matrices $A_t = a_t I_N$ with scalar survival factor $a_t \in (0, 1]$, input-to-state vector $b_t \in \mathbb{R}^N$, and state-to-output vector $c_t \in \mathbb{R}^N$:
Notice the exact algebraic duality: replacing softmax with a rank-1 separable decay mask $L_{t,s}$ and identifying $(C, B, X)$ with $(Q, K, V)$ turns a recurrent SSM into causal masked linear attention!
Why Scalar-Times-Identity $A_t = a_t I_N$ Unlocks Tensor Cores
In Mamba-1, each channel $p \in \{1..P\}$ had an independent diagonal matrix $A_t^{(p)} \in \mathbb{R}^N$, preventing matrix multiplication across head dimensions. Restricting $A_t = a_t I_N$ to a scalar decay per head shares the lower-triangular decay mask $L \in \mathbb{R}^{T \times T}$ across all state and head features, reducing the quadratic dual pass to standard torch.matmul calls at $100+$ TFLOP/s on Tensor Cores.
torch.compile Footguns in SSD:
(1) Computing $L_{t,s} = \exp(\text{cumsum}(\ln a)_t - \text{cumsum}(\ln a)_s)$ directly across long sequences causes exp(+large) = Inf in the upper triangle before masking ($s \gt t$), producing 0.0 * Inf = NaN in backward gradients – always clamp the exponent difference to $\le 0$ before calling torch.exp.
(2) Interleaving Mamba-2 layers with full-attention layers (usually at a 7:1 ratio) recovers exact needle-in-a-haystack in-context copying where fixed-state SSMs bottleneck (Waleffe et al., arXiv:2406.07887).
1. PyTorch Verification: Exact Duality Between Quadratic Attention and Linear Recurrence
The self-contained snippet below proves numerically that the quadratic $1$-semiseparable attention formulation and the step-by-step $O(1)$-memory linear recurrence produce identical outputs to within $10^{-15}$ double-precision floating-point tolerance:
💻 Python: State Space Duality (SSD) Quadratic vs. Recurrent EquivalencePyTorch
import math
import torch
import torch.nn.functional as F
def ssd_quadratic_dual(
X: torch.Tensor, B_mat: torch.Tensor, C_mat: torch.Tensor, a_log_decay: torch.Tensor
) -> torch.Tensor:
"""Quadratic Tensor-Core dual view: Y = (L * (C @ B^T)) @ X (Dao & Gu, arXiv:2405.21060)."""
# X: [B, T, H, P], B_mat: [B, T, H, N], C_mat: [B, T, H, N], a_log_decay: [B, T, H] (<= 0)
T = X.size(1)
csum = torch.cumsum(a_log_decay, dim=1) # [B, T, H]
diff = csum.unsqueeze(2) - csum.unsqueeze(1) # [B, T, T, H]
causal_mask = torch.tril(torch.ones(T, T, device=X.device, dtype=torch.bool))[None, :, :, None]
# Clamp exponent <= 0 BEFORE exp() so upper-triangular (s > t) entries never overflow to Inf
L_semisep = torch.where(causal_mask, torch.exp(diff.clamp(max=0.0)), torch.zeros_like(diff))
M = L_semisep * torch.einsum("bthn,bshn->btsh", C_mat, B_mat) # [B, T, T, H]
return torch.einsum("btsh,bshp->bthp", M, X) # [B, T, H, P]
def ssd_linear_recurrent(
X: torch.Tensor, B_mat: torch.Tensor, C_mat: torch.Tensor, a_log_decay: torch.Tensor
) -> torch.Tensor:
"""Primal recurrent view with O(1) state memory h_t in R^{N x P}."""
B, T, H, P = X.shape
N = B_mat.size(-1)
h_state = torch.zeros(B, H, N, P, device=X.device, dtype=X.dtype)
outputs = []
for t in range(T):
decay = torch.exp(a_log_decay[:, t, :]).view(B, H, 1, 1)
h_state = decay * h_state + torch.einsum("bhn,bhp->bhnp", B_mat[:, t], X[:, t])
outputs.append(torch.einsum("bhn,bhnp->bhp", C_mat[:, t], h_state))
return torch.stack(outputs, dim=1) # [B, T, H, P]
if __name__ == "__main__":
torch.manual_seed(42)
B_sz, T_len, H_heads, N_state, P_dim = 2, 16, 4, 8, 16
X_in = torch.randn(B_sz, T_len, H_heads, P_dim, dtype=torch.float64)
B_in = torch.randn(B_sz, T_len, H_heads, N_state, dtype=torch.float64) / math.sqrt(N_state)
C_in = torch.randn(B_sz, T_len, H_heads, N_state, dtype=torch.float64) / math.sqrt(N_state)
a_in = -F.softplus(torch.randn(B_sz, T_len, H_heads, dtype=torch.float64))
y_quad = ssd_quadratic_dual(X_in, B_in, C_in, a_in)
y_lin = ssd_linear_recurrent(X_in, B_in, C_in, a_in)
print(f"[PASS] Output Tensor Shape : {tuple(y_quad.shape)}")
print(f"[PASS] SSD Quadratic vs. Linear Max Abs Error : {(y_quad - y_lin).abs().max().item():.2e}")
# Output:
# [PASS] Output Tensor Shape : (2, 16, 4, 16)
# [PASS] SSD Quadratic vs. Linear Max Abs Error : 1.55e-15
2. Long-Context Sequence Architectures: Head-to-Head
| Architecture | Training FLOPs | Decode KV / State Bytes per Token | Tensor Core Utilization & Copying Fidelity |
|---|---|---|---|
| FlashAttention-2 + GQA (Ref) | $O(T^2 d)$ | $O(T \cdot g \cdot d_h)$ (grows linearly with $T$) | High GEMM utilization; exact in-context retrieval |
| Ring Attention (arXiv:2310.01889) | $O(T^2 d / D_{\text{ring}})$ | Distributed across $D_{\text{ring}}$ hosts via P2P overlap | Hides network latency when chunk $T_c \ge \text{FLOP/BW threshold}$ |
| Mamba-1 (Selective Scan) | $O(T N P)$ | $O(1)$ fixed state ($N \times P$ per layer) | Memory-bound custom CUDA scan; no Tensor Core MMA |
| Mamba-2 (SSD, arXiv:2405.21060) | $O(T Q N)$ | $O(1)$ fixed state ($N = 64\text{–}128$ practical) | $2\text{–}8\times$ faster via blockwise GEMM; best in 7:1 Hybrid GQA |