State Space Model (SSM)

At its core, an SSM defines a continuous-time system using a state equation and an observation equation. The system evolves a hidden state h(t) based on the input x(t) through learned matrices (A, B, C, D). Unlike transformers, this formulation processes sequences with O(N) linear complexity rather than quadratic, making it inherently scalable to chromosome-length sequences spanning millions of base pairs. The HiPPO matrix (High-order Polynomial Projection Operators) provides a mathematically optimal initialization for the state transition matrix A, enabling the model to memorize long-range dependencies by compressing input history into an orthogonal polynomial basis.

The Mamba architecture introduces a critical innovation over traditional SSMs: input-dependent parameters. Unlike earlier models (S4, H3) where matrices A, B, and C are fixed for all inputs, Mamba makes B and C functions of the current token. This selective state space allows the model to filter irrelevant information and focus on pertinent genomic features dynamically. For example, when scanning a gene locus, the model can selectively retain exon boundary signals while discarding intronic noise. This selection is implemented via a parallel scan algorithm on modern GPU hardware, achieving efficient training despite the recurrent formulation.

To process discrete nucleotide tokens (A, C, G, T), the continuous-time SSM must be converted into a discrete recurrence. This discretization step uses a learnable step size Δ and a formula such as the bilinear transform or zero-order hold to convert continuous matrices (A, B) into their discrete counterparts (Ā, B̄). The step size Δ acts as a gate, controlling how much the current input influences the hidden state. In genomic applications, a larger Δ allows the model to focus sharply on a splice site or start codon, while a smaller Δ enables smooth integration of broader chromatin context.

A naive recurrent implementation of SSMs is slow on GPUs due to sequential dependencies. Mamba overcomes this with a hardware-aware parallel scan algorithm implemented in Triton or custom CUDA kernels. The scan computes the full sequence of hidden states efficiently by performing a prefix sum operation on a parallel processor. Crucially, intermediate states are materialized in fast SRAM rather than slower HBM (High Bandwidth Memory), avoiding the memory bottleneck that plagues attention-based models. This kernel fusion strategy enables processing of 1-million-token genomic sequences without memory overflow.

SSMs excel on tasks requiring synthetic long-range reasoning that confound transformers. On the Long Range Arena (LRA) benchmark, S4 and Mamba achieve near-perfect accuracy on the Path-X task (classifying 16,384-pixel images), where standard transformers fail entirely. In genomics, this translates to directly modeling enhancer-gene interactions spanning hundreds of kilobases without truncating the input. SSMs can ingest an entire topologically associating domain (TAD) as a single sequence, learning regulatory grammar across distal elements that are separated by vast intergenic distances.

For efficient training, the linear time-invariant SSM can be expressed as a global convolution between the input sequence and a fixed kernel derived from the SSM parameters. This allows the entire sequence to be processed in parallel during training using Fast Fourier Transforms (FFTs). The convolutional kernel implicitly encodes the model's long-range memory profile. During inference, the model switches to its recurrent mode, generating predictions token-by-token with constant memory. This dual representation—convolutional for training, recurrent for inference—provides the best of both paradigms for genomic foundation models.

The defining computational advantage of SSMs over standard attention mechanisms. While self-attention scales quadratically with sequence length O(L²), SSMs achieve linear complexity O(L) by maintaining a compressed hidden state that summarizes all prior history. This enables processing of whole human chromosomes (millions of base pairs) in a single forward pass without chunking or approximation strategies required by transformer-based genomic models.

The key innovation in the Mamba architecture that distinguishes it from earlier SSMs like S4. Traditional SSMs use time-invariant parameters (A, B, C matrices are fixed regardless of input). Mamba introduces input-dependent selectivity, where the state transition parameters become functions of the current token. This allows the model to selectively propagate or forget information—analogous to an attention gate—while retaining linear complexity. For genomics, this means the model can learn to ignore intronic regions while focusing on coding sequences and regulatory elements.

An alternative sub-quadratic architecture that replaces self-attention with implicit long convolutions parameterized by a multiplicative gating mechanism. Hyena achieves O(N log N) complexity by interleaving long convolutional filters with element-wise gating operations. Unlike SSMs which maintain an explicit recurrent state, Hyena uses a convolutional mode for efficient training and can match transformer quality on genomic benchmarks while being significantly faster for sequences exceeding 100k base pairs.

The mathematical foundation for high-quality SSM state representations. HiPPO (High-order Polynomial Projection Operators) theory defines a class of matrices that optimally compress continuous signal history into a fixed-dimensional state vector. The HiPPO-LegS (Legendre Scaled) matrix ensures the state captures information uniformly across all timescales, preventing the exponential forgetting of distant past tokens. This initialization is critical for SSMs to model ultra-long-range dependencies in genomic sequences without gradient vanishing.

The algorithmic technique that makes SSM training efficient on GPUs despite their recurrent formulation. Instead of sequential recurrence, the linear state update is reformulated as a parallel prefix scan operation, enabling computation across all sequence positions simultaneously. Mamba's implementation uses kernel fusion to avoid materializing the full state matrix in GPU memory, achieving wall-clock speeds competitive with optimized FlashAttention implementations while processing sequences orders of magnitude longer.