π Sub-Quadratic Scaling: From Approximate Matrices to Continuous Dynamical Systems
While exact hardware-tiled algorithms like FlashAttention resolve GPU memory bandwidth bottlenecks and eliminate the intermediate memory footprint of the attention matrix, they do not alter the underlying computational FLOP complexity: computing pairwise interactions across sequence length $N$ remains fundamentally $\mathcal{O}(N^2 d)$. When context lengths push into hundreds of thousands or millions of tokens (whole code repositories, hours of high-rate audio, long video streams), quadratic compute scaling becomes computationally prohibitive. Efficient Attention Architectures attack this scaling ceiling through algorithmic restructuring: Sparse Attention & Longformer exploit local sliding windows with global anchor tokens to construct $\mathcal{O}(N \cdot k)$ band matrices; Linformer applies Johnson-Lindenstrauss low-rank projection down to $\mathcal{O}(N \cdot k)$; Kernelized Linear Attention uses feature map duality to invert the matrix multiplication order, dropping complexity to $\mathcal{O}(N d^2)$; and Selective State Space Models (Mamba) replace discrete pairwise routing altogether with time-varying continuous linear dynamical systems, achieving strictly linear $\mathcal{O}(N)$ compute scaling, constant $\mathcal{O}(1)$ inference state memory, and parallel hardware associative scans.
THE EFFICIENT ATTENTION LANDSCAPE:
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β EFFICIENT ATTENTION MECHANISMS β
βββββββββββββββββββββββββββββ¬βββββββββββββββββββββββββββββ
β
ββββββββββββββββββββββββββββ¬ββββββββββββββββββββββββ΄ββββββββββββββββ¬βββββββββββββββββββββββββββ
βΌ βΌ βΌ βΌ
ββββββββββββββββββββ ββββββββββββββββββββ ββββββββββββββββββββ ββββββββββββββββββββ
β SPARSE PATTERNS β β LOW-RANK β β KERNEL TRICK β β STATE SPACE β
β (Band / Strided) β β PROJECTIONS β β (Associative Law)β β MODELS (SSMs) β
βββββββββ¬βββββββββββ ββββββββββ¬ββββββββββ ββββββββββ¬ββββββββββ ββββββββββ¬ββββββββββ
β β β β
βββΊ Local Window βββΊ Linformer (Wang et al.) βββΊ Linear Attn βββΊ S4 (Gu et al.)
β Sliding window w β Projects K, V from β (Katharopoulos et al.)β HiPPO Matrix
β β N β k (Fixed rank) β Softmax β Ο(Q)Β·Ο(K)^T β Structured state
βββΊ Longformer (Beltagy) β β β
β Sliding + Dilated βββΊ NystrΓΆmformer βββΊ Performer (Choromanskiβ βββΊ Mamba (Gu & Dao)
β + Global Anchors Landmark anchor NystrΓΆm Random Fourier β Selective Scan
β approximations Features (FAVOR+) β Hardware-aware
βββΊ BigBird (Zaheer) β Linear O(N)
Window + Random ββββββββββββββββββ
+ Global tokens
THE LONGFORMER COMPOUND SPARSE ATTENTION PATTERNS (Beltagy et al., 2020):
Sequence Length N = 8, Window size w = 2, Global Tokens = [Position 0]
(A) SLIDING WINDOW (Local): (B) DILATED SLIDING (Gaps): (C) COMPOUND LONGFORMER (A + B + Global):
Attends strictly to w neighbors. Attends with stride d = 2. Global tokens attend to ALL; all attend to Global.
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
0 [β β Β· Β· Β· Β· Β· Β·] 0 [β Β· β Β· Β· Β· Β· Β·] 0 [β β β β β β β β ] βββ Global Token [CLS]
1 [β β β Β· Β· Β· Β· Β·] 1 [Β· β Β· β Β· Β· Β· Β·] 1 [β β β Β· Β· Β· Β· Β·]
2 [Β· β β β Β· Β· Β· Β·] 2 [β Β· β Β· β Β· Β· Β·] 2 [β β β β Β· Β· Β· Β·]
3 [Β· Β· β β β Β· Β· Β·] 3 [Β· β Β· β Β· β Β· Β·] 3 [β Β· β β β Β· Β· Β·]
4 [Β· Β· Β· β β β Β· Β·] 4 [Β· Β· β Β· β Β· β Β·] 4 [β Β· Β· β β β Β· Β·]
5 [Β· Β· Β· Β· β β β Β·] 5 [Β· Β· Β· β Β· β Β· β ] 5 [β Β· Β· Β· β β β Β·]
6 [Β· Β· Β· Β· Β· β β β ] 6 [Β· Β· Β· Β· β Β· β Β·] 6 [β Β· Β· Β· Β· β β β ]
7 [Β· Β· Β· Β· Β· Β· β β ] 7 [Β· Β· Β· Β· Β· β Β· β ] 7 [β Β· Β· Β· Β· Β· β β ]
β²
βββ Global Column Connection
COMPLEXITY COMPARISON:
β’ Standard Full Attention : Memory & Compute = O(N^2)
β’ Longformer Attention : Memory & Compute = O(N Β· (w + g)) where w = window size, g = global tokens count
For N = 65,536, w = 512, g = 4: Flops reduced by > 98.5%!
[CLS] or question tokens in QA tasks) attend to every token across the full document, and every token attends back to them, preserving cross-document reasoning while keeping overall complexity linear with sequence length: $\mathcal{O}(N(w + g))$.THE LINFORMER LOW-RANK ATTENTION ENGINE (Wang et al., 2020):
THEORETICAL FOUNDATION (JOHNSON-LINDENSTRAUSS LEMMA & SVD):
The post-softmax attention matrix P = Softmax(Q K^T / βd) β R^{N Γ N} is low-rank!
Singular value spectrum analysis shows that most eigenvalues decay rapidly:
The effective rank of P is bounded by k = O(d_model / Ξ΅^2), completely INDEPENDENT of sequence length N!
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
ARCHITECTURAL PROJECTION OPERATORS:
Introduce learned projection matrices E, F β R^{k Γ N} that project the SEQUENCE dimension down to k:
1. Standard Projections:
Q = X Β· W_Q β R^{N Γ d_k}
K = X Β· W_K β R^{N Γ d_k}
V = X Β· W_V β R^{N Γ d_v}
2. Low-Rank Key & Value Compressions:
K_projected = E Β· K β R^{k Γ d_k} (Down-projects sequence dimension from N β k)
V_projected = F Β· V β R^{k Γ d_v} (Down-projects sequence dimension from N β k)
3. Low-Rank Scaled Dot-Product Attention:
Linformer(Q, K, V) = Softmax β Q Β· (E Β· K)^T β Β· (F Β· V)
β βββββββββββββ β
β βd_k β
Dimensions:
β’ Q Β· (E Β· K)^T : Shape (N Γ d_k) Β· (d_k Γ k) = (N Γ k) <-- Matrix is N Γ k instead of N Γ N!
β’ Softmax( Β· ) : Shape (N Γ k)
β’ Context Output : Shape (N Γ k) Β· (k Γ d_v) = (N Γ d_v)
COMPLEXITY REDUCTION:
β’ Compute Complexity: O(N Β· k Β· d_k) = O(N) (Linear in sequence length N!)
β’ Memory Complexity: O(N Β· k) = O(N) (Zero N Γ N intermediate tensors!)
THE KERNELIZED LINEAR ATTENTION DERIVATION:
STANDARD ATTENTION FORMULATION:
Row i of the attention output is:
β_{j=1}^N sim(q_i, k_j) Β· v_j
O_i = βββββββββββββββββββββββββββββββββββββββββ
β_{j=1}^N sim(q_i, k_j)
where standard attention defines sim(q_i, k_j) = exp(q_i^T k_j / βd).
Because the exponential function exp(Β·) ties q_i and k_j non-linearly inside the Softmax,
we MUST evaluate the full N Γ N pairwise score matrix before multiplying by V!
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
THE KERNEL DECOMPOSITION TRICK:
Replace exp(q^T k) with a kernel similarity function defined by feature maps Ο(Β·):
sim(q, k) = Ο(q)^T Β· Ο(k) where Ο(x) = elu(x) + 1 or Ο(x) = relu(x)
Substitute back into the output equation:
β_{j=1}^N ( Ο(q_i)^T Β· Ο(k_j) ) Β· v_j
O_i = βββββββββββββββββββββββββββββββββββββββββββββββ
β_{j=1}^N ( Ο(q_i)^T Β· Ο(k_j) )
APPLY THE ASSOCIATIVE LAW OF MATRIX MULTIPLICATION:
Move the query term Ο(q_i)^T outside the inner summation over j!
Ο(q_i)^T Β· [ β_{j=1}^N Ο(k_j) Β· v_j^T ]^T
O_i = ββββββββββββββββββββββββββββββββββββββββββββββββββ
Ο(q_i)^T Β· [ β_{j=1}^N Ο(k_j) ]
COMPUTATIONAL PAIRING COMPARISON:
Standard Attention: ( Q Β· K^T ) Β· V β Matrix sizes: (N Γ N) Γ (N Γ d) = O(N^2 Β· d)
Linear Kernel Attention: Ο(Q) Β· ( Ο(K)^T Β· V ) β Matrix sizes: (N Γ d) Γ [ (d Γ N) Γ (N Γ d) ]
= (N Γ d) Γ (d Γ d) = O(N Β· d^2) !
THE STATE SPACE MODEL (SSM) CONTINUOUS-TO-DISCRETE PIPELINE:
1. CONTINUOUS-TIME STATE SPACE REPRESENTATION:
Maps a 1D continuous input signal x(t) to an N-dimensional continuous hidden state h(t),
emitting an output signal y(t):
h'(t) = A Β· h(t) + B Β· x(t) (State transition ODE)
y(t) = C Β· h(t) + D Β· x(t) (Output observation mapping)
where A β R^{N Γ N} (State evolution matrix), B β R^{N Γ 1}, C β R^{1 Γ N}, D β R^1.
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
2. DISCRETIZATION VIA ZERO-ORDER HOLD (ZOH) WITH STEP SIZE Ξ:
Transforms continuous differential operators into discrete parameters (A_bar, B_bar):
A_bar = exp(Ξ Β· A)
B_bar = (Ξ Β· A)^{-1} Β· (exp(Ξ Β· A) - I) Β· (Ξ Β· B)
DISCRETE FORM 1: RECURRENT MODE (Fast O(1) Real-Time Inference!):
h_k = A_bar Β· h_{k-1} + B_bar Β· x_k
y_k = C Β· h_k + D Β· x_k
DISCRETE FORM 2: CONVOLUTIONAL MODE (Parallelized O(N log N) Training on GPUs!):
Unrolling the recurrence reveals a global 1D convolution over input sequence x:
y = x β K_bar where K_bar = (C B_bar, C A_bar B_bar, C A_bar^2 B_bar, ...)
Computed across all N steps in parallel using Fast Fourier Transforms (FFT)!
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
3. THE HiPPO MATRIX INITIALIZATION (Gu et al., 2020):
Why standard random initialization fails: Recurrent states forget historical inputs over long horizons.
HiPPO (High-order Polynomial Projection Operators) defines an optimal mathematical matrix A
that maintains an orthogonal Legendre polynomial projection of all historical inputs x(t)
with exponential memory retention over tens of thousands of time steps.
THE SELECTIVE MECHANISM IN MAMBA (Gu & Dao, 2023):
THE LTI FLAW: In S4, matrices (A, B, C, Ξ) are static and independent of input tokens.
A model cannot selectively remember relevant tokens ("Paris", "Einstein") or discard irrelevant
filler words ("the", "um"). It processes all tokens identically!
MAMBA'S INPUT-DEPENDENT PARAMETER PROJECTION:
Make transition parameters explicit linear functions of current input token x_t:
Input Token x_t β R^{B Γ L Γ d}
β
βββββββββββββββββββββββΌββββββββββββββββββββββ
βΌ Linear Projection βΌ Linear Projection βΌ Linear Projection
B_t = W_B(x_t) C_t = W_C(x_t) Ξ_t = Softplus( Parameter + W_Ξ(x_t) )
(Selects what to (Selects what to (Input-dependent gate: Controls how much
write to state) read from state) to update state vs. retain previous state!)
β β β
βββββββββββββββββββββββΌββββββββββββββββββββββ
βΌ Dynamic Discretization
A_bar_t = exp( Ξ_t Β· A ), B_bar_t = Ξ_t Β· B_t (Now time-varying!)
β
βΌ Selective Recurrence Step
h_t = A_bar_t Β· h_{t-1} + B_bar_t Β· x_t
y_t = C_t Β· h_t
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
THE HARDWARE-AWARE FUSED PARALLEL SCAN:
Because parameters change at every step, convolution via FFT is NO LONGER MATHEMATICALLY POSSIBLE!
Solution: Implement an exact **Parallel Associative Prefix Scan** in GPU SRAM:
β’ Instead of stepping sequentially in slow HBM, tiles inputs directly into fast on-chip SRAM.
β’ Computes tree reductions over states in parallel in O(log N) depth.
β’ Fuses discretization, scan, and output projections into a single CUDA kernel, yielding 5x higher throughput!
import math
import torch
import torch.nn as nn
import torch.nn.functional as F
# ==============================================================================
# 1. KERNELIZED LINEAR ATTENTION MODULE (Katharopoulos et al., 2020)
# Uses feature map Ο(x) = elu(x) + 1 to invert matrix multiplication order: O(N)
# ==============================================================================
class LinearAttention(nn.Module):
def __init__(self, d_model: int, num_heads: int):
super().__init__()
assert d_model % num_heads == 0
self.d_model = d_model
self.num_heads = num_heads
self.head_dim = d_model // num_heads
self.w_q = nn.Linear(d_model, d_model, bias=False)
self.w_k = nn.Linear(d_model, d_model, bias=False)
self.w_v = nn.Linear(d_model, d_model, bias=False)
self.w_o = nn.Linear(d_model, d_model, bias=False)
@staticmethod
def feature_map(x: torch.Tensor) -> torch.Tensor:
"""Applies positive non-linear feature map: Ο(x) = ELU(x) + 1.0"""
return F.elu(x) + 1.0
def forward(self, x: torch.Tensor) -> torch.Tensor:
b, s, _ = x.shape
# 1. Linear Projections and 4D Reshape: (B, H, S, D)
q = self.feature_map(self.w_q(x).view(b, s, self.num_heads, self.head_dim).transpose(1, 2))
k = self.feature_map(self.w_k(x).view(b, s, self.num_heads, self.head_dim).transpose(1, 2))
v = self.w_v(x).view(b, s, self.num_heads, self.head_dim).transpose(1, 2)
# 2. Invert Matrix Multiplication Order: Compute KV Memory Buffer M first!
# k: (B, H, S, D), v: (B, H, S, D)
# KV Memory Buffer: (B, H, D, S) x (B, H, S, D) -> (B, H, D, D)
kv = torch.matmul(k.transpose(-2, -1), v)
# Normalization denominator vector: (B, H, D, S) x (B, H, S, 1) -> (B, H, D, 1)
z = k.sum(dim=-2, keepdim=True).transpose(-2, -1) # Sum keys across sequence
# 3. Compute Output: q @ KV -> (B, H, S, D) x (B, H, D, D) -> (B, H, S, D)
numerator = torch.matmul(q, kv)
# Normalization factor per query token: q @ z -> (B, H, S, D) x (B, H, D, 1) -> (B, H, S, 1)
denominator = torch.matmul(q, z) + 1e-6
# Scale output by denominator
out = numerator / denominator
# 4. Recombine Heads and Project Out
out = out.transpose(1, 2).contiguous().view(b, s, self.d_model)
return self.w_o(out)
# ==============================================================================
# 2. TOY SELECTIVE STATE SPACE (MAMBA) RECURRENT LAYER
# Demonstrates input-dependent parameterization (B(x), C(x), Ξ(x))
# ==============================================================================
class ToyMambaSSM(nn.Module):
def __init__(self, d_model: int, state_dim: int = 16):
super().__init__()
self.d_model = d_model
self.state_dim = state_dim
# Input-dependent projections for B, C, and Delta
self.x_proj = nn.Linear(d_model, state_dim * 2 + 1, bias=False)
self.dt_proj = nn.Linear(1, d_model, bias=True)
# Learnable log-space State matrix A: Shape (d_model, state_dim)
A = torch.arange(1, state_dim + 1, dtype=torch.float32).repeat(d_model, 1)
self.A_log = nn.Parameter(torch.log(A)) # Initialized to standard HiPPO structure
self.D = nn.Parameter(torch.ones(d_model)) # Skip connection parameter
def forward(self, x: torch.Tensor) -> torch.Tensor:
"""
x: Input tensor of shape (Batch_Size, Seq_Len, d_model)
Returns: Processed tensor of shape (Batch_Size, Seq_Len, d_model)
"""
b, s, d = x.shape
device = x.device
# Invert A from log space: Ensure A is strictly negative for stability
A = -torch.exp(self.A_log) # (d_model, state_dim)
# 1. Project input to derive dynamic B, C, and raw Delta
ssm_params = self.x_proj(x) # (B, S, 2*state_dim + 1)
B = ssm_params[:, :, :self.state_dim] # (B, S, state_dim)
C = ssm_params[:, :, self.state_dim:2*self.state_dim] # (B, S, state_dim)
dt_raw = ssm_params[:, :, -1:] # (B, S, 1)
# Project and discretize Delta: (B, S, d_model)
delta = F.softplus(self.dt_proj(dt_raw))
# 2. Execute Recurrent Sequential Scan over tokens
y = torch.zeros(b, s, d, device=device)
h = torch.zeros(b, d, self.state_dim, device=device) # Initial hidden state
for t in range(s):
x_t = x[:, t, :] # (B, d)
delta_t = delta[:, t, :] # (B, d)
B_t = B[:, t, :] # (B, state_dim)
C_t = C[:, t, :] # (B, state_dim)
# Continuous-to-Discrete Zero-Order Hold Approximation:
# A_bar = exp(delta * A) -> Shape: (B, d, state_dim)
dA = torch.exp(delta_t.unsqueeze(-1) * A.unsqueeze(0))
# B_bar = delta * B -> Shape: (B, d, state_dim)
dB = delta_t.unsqueeze(-1) * B_t.unsqueeze(1)
# Recurrent State Update: h_t = A_bar * h_{t-1} + B_bar * x_t
h = dA * h + dB * x_t.unsqueeze(-1)
# Output Projection: y_t = h_t Β· C_t + D * x_t
# (B, d, state_dim) x (B, state_dim, 1) -> (B, d)
y_t = torch.matmul(h, C_t.unsqueeze(-1)).squeeze(-1) + self.D * x_t
y[:, t, :] = y_t
return y
# ------------------------------------------------------------------------------
# Runtime Execution & Computational Benchmark
# ------------------------------------------------------------------------------
if __name__ == "__main__":
torch.manual_seed(42)
device = torch.device("cuda" if torch.cuda.is_available() else "cpu")
B, S, D, H, N_state = 2, 64, 128, 4, 16
print("[*] Initializing Efficient Attention & Mamba Verification Suite...")
lin_attn = LinearAttention(d_model=D, num_heads=H).to(device)
mamba_ssm = ToyMambaSSM(d_model=D, state_dim=N_state).to(device)
# Input tensor
input_data = torch.randn(B, S, D, device=device, requires_grad=True)
# 1. Forward Pass: Linear Attention
out_linear = lin_attn(input_data)
print(f"[β] Linear Attention Executed Successfully:")
print(f" β’ Output Shape : {out_linear.shape} (Expected: [{B}, {S}, {D}])")
# 2. Forward Pass: Toy Mamba Selective State Space
out_mamba = mamba_ssm(input_data)
print(f"[β] Mamba Selective SSM Executed Successfully:")
print(f" β’ Output Shape : {out_mamba.shape} (Expected: [{B}, {S}, {D}])")
# 3. Backward Pass Verification
loss = (out_linear.sum() + out_mamba.sum())
loss.backward()
print(f"[β] Backward Propagation Computed:")
print(f" β’ Input Gradient Norm: {input_data.grad.norm().item():.4f}")
EFFICIENT ATTENTION & SSM ANOMALIES & REMEDIATIONS:
1. THE LINEAR ATTENTION UNNORMALIZED DENOMINATOR COLLAPSE:
β’ Symptom: Training diverges at step 50; loss returns NaN or large activations spike to 1e5.
β’ Cause: The denominator in kernel attention: q_i Β· β Ο(k_j) can evaluate to near-zero (0.0)
if feature map values are small. Dividing by 0.0 results in infinite gradients!
β’ Remediation: Always clamp the denominator with an explicit numerical epsilon:
denominator = torch.clamp(torch.matmul(q, z), min=1e-6)
2. STATE EXPLOSION IN STATE SPACE DISCRETIZATION (UNSTABLE A MATRIX):
β’ Symptom: The hidden state h_t in SSMs blows up exponentially across time: ||h_1000|| >> 1e10.
β’ Theoretical Cause: Real parts of eigenvalues of state transition matrix A must be STRICTLY NEGATIVE:
Re(Ξ»_i(A)) < 0. If any eigenvalue is positive, exp(Ξ Β· A) > 1.0, turning the recurrence into an
explosive feedback loop!
β’ Remediation: Parameterize A as negative exponential: A = -torch.exp(A_log), or enforce the
analytical HiPPO matrix initialization directly.
3. ASSOCIATIVE MEMORY RETRIEVAL FAILURE (THE "NEEDLE-IN-A-HAYSTACK" DEFECT):
β’ Symptom: A linear model or SSM achieves high language modeling perplexity, but fails completely on
long-context retrieval benchmarks (e.g. copying an exact UUID placed 50k tokens back in context).
β’ Cause: Pure SSMs compress infinite history into a finite hidden state vector h β R^N.
Unlike standard Transformers that use pairwise dot products to access the exact historical token,
the SSM state acts as a lossy continuous compression reservoir.
β’ Remediation: Deploy Hybrid Architectures (e.g., Jamba / Zamba): Interleave 1 standard Attention
layer for every 6 to 8 Mamba layers to provide precise associative retrieval capabilities!
EFFICIENT ATTENTION & STATE SPACE SPECIFICATION MATRIX:
βββββββββββββββββββββββββββ¬βββββββββββββββββββββββββββββββ¬βββββββββββββββββββ¬ββββββββββββββββββββββββββββββββ
β ARCHITECTURE FAMILY β MATHEMATICAL MECHANISM β COMPUTATIONAL β INFERENCE RECURRENT MEMORY β
β β β COMPLEXITY (FLOP)β STATE FOOTPRINT β
βββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββΌββββββββββββββββββββββββββββββββ€
β Standard Transformer β Softmax(Q K^T / βd) Β· V β O(N^2 Β· d) β O(N Β· d) Linear KV-Cache β
β (Vaswani et al., 2017) β Exact Pairwise Attention β Quadratic Bound β (Exhausts VRAM on long ctx) β
βββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββΌββββββββββββββββββββββββββββββββ€
β Longformer β Local Window w + Dilation d β O(N Β· (w + g)) β O(w Β· d) Sliding Window Cache β
β (Beltagy et al., 2020) β + Global Anchor Tokens β Strictly Linear β (Bounded by window size w) β
βββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββΌββββββββββββββββββββββββββββββββ€
β Linformer β Low-rank Sequence Projection β O(N Β· k Β· d) β Fixed-length Projection E, F β
β (Wang et al., 2020) β EΒ·K and FΒ·V down to rank k β Strictly Linear β (Cannot extend past Max_Len N)β
βββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββΌββββββββββββββββββββββββββββββββ€
β Kernel Linear Attention β Feature map Ο(Q)Β·(Ο(K)^TΒ·V) β O(N Β· d^2) β O(d^2) Constant Memory State β
β (Katharopoulos et al.) β Inverted Matrix Association β Linear in N β (Zero sequence-length growth!)β
βββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββΌββββββββββββββββββββββββββββββββ€
β Structured State Space β HiPPO continuous-time ODE β O(N log N) Train β O(N_state) Constant State β
β (S4 - Gu et al., 2021) β Discretized LTI Convolution β O(1) Inference β (Linear Time-Invariant model) β
βββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββΌββββββββββββββββββββββββββββββββ€
β Mamba (Selective SSM) β Input-dependent B(x), C(x), Ξβ O(N) Compute β O(d Β· N_state) Constant State β
β (Gu & Dao, 2023) β Fused GPU Parallel Scan β Strictly Linear β (Zero KV-Cache memory growth!)β
βββββββββββββββββββββββββββ΄βββββββββββββββββββββββββββββββ΄βββββββββββββββββββ΄ββββββββββββββββββββββββββββββββ€
β TOP 5 EFFICIENT ATTENTION AXIOMS FOR AI ENGINEERS: β
β 1. The Kernel Inversion Law: Factoring the Softmax kernel into Ο(Q)Β·Ο(K)^T allows moving summation order β
β to evaluate (K^T Β· V) first, slashing computational complexity from O(N^2 d) down to O(N d^2). β
β 2. Associativity Enables Linear Inference: Linear attention models and SSMs maintain a fixed-size state β
β matrix, eliminating the linear growth of the KV-cache during autoregressive token generation. β
β 3. Selective Gating Breaks LTI: Mamba achieves Transformer-level reasoning by making state space β
β matrices input-dependent (B(x), C(x), Ξ(x)), allowing the model to filter out irrelevant context. β
β 4. Hardware Awareness Dictates Adoption: Theoretical linear complexity fails if it cannot map onto dense β
β GPU SRAM operations; Mamba succeeds because its parallel scan is fused directly on-chip. β
β 5. Hybrid Models Deliver Peak Performance: Combining 85% Mamba layers with 15% sparse attention layers β
β yields sub-quadratic execution throughput while maintaining exact in-context associative recall. β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ