AI/ML State Space Models Mamba-2 Ring Attention PyTorch

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$:

Primal Recurrent View ($O(T)$ Complexity) vs. Dual Quadratic Attention View ($O(T^2)$ Tensor Core GEMM)
$$h_t = a_t\, h_{t-1} + b_t\, x_t^\top \in \mathbb{R}^{N \times P}, \qquad y_t = c_t^\top h_t = \sum_{s=0}^{t} \left(\prod_{k=s+1}^{t} a_k\right) (c_t^\top b_s)\, x_s$$ $$Y = M X, \qquad M = L \odot (C B^\top), \qquad L_{t, s} = \begin{cases} \exp\!\left(\sum_{k=s+1}^{t} \ln a_k\right) & t \ge s \\ 0 & t \lt s \end{cases}$$

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.

1. Intra-Chunk Diagonal Blocks (Quadratic Dual) Chunk size Q = 64..256 → Tensor Core GEMM: Y_diag = (L ⊙ C B^T) X Chunk 0 Low-Rank Chunk 1 FLOPs: O(T · Q · N) with high arithmetic intensity 2. Inter-Chunk State Scan (Linear Primal) Pass compressed state h_c ∈ ℝ^(N×P) across T/Q chunk boundaries State h₀ State h₁ State h₂ O(1) Inference Memory – No KV-Cache Growth with T
Figure 1: Structured State Space Duality (SSD) decomposes sequence transformation into Tensor-Core-friendly intra-chunk quadratic blocks of size $Q$ and a lightweight recurrent scan over inter-chunk boundary states $h_c \in \mathbb{R}^{N \times P}$.
Numerical Underflow & 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