Sequence models and state spaces

Consider one scalar input u_t and a state h_t of width N. A discrete linear time-invariant model uses an N by N transition matrix, an N-dimensional input map, and a readout vector. The state contains every retained effect of the past. With a stable transition, older inputs often decay; this helps numerical behavior but can also erase useful information. A state of fixed width has a fixed storage budget at inference, whereas a conventional attention cache grows with the sequence.

Continuous-time state equations are often discretized before processing sampled data. The sampling interval and discretization rule matter: multiplying a continuous matrix by a step size is not generally the exact discrete transition. Structured parameterizations can make transitions and kernel computation efficient. A generic dense N by N matrix update still costs order N² per token, so sequence-linear complexity alone does not establish a small constant factor or good hardware utilization.

Starting from zero state, substitute the recurrence into itself. The current output becomes a weighted sum of earlier inputs with weights determined by powers of the transition matrix. Because fixed coefficients depend on lag rather than absolute position, these weights form a causal convolution kernel. This gives different computational views of the same linear operation: recurrent updates for streaming and structured kernel or scan methods for parallel training.

Selective state-space models make parts of the update depend on the current input so the model can choose what to retain or forget. This breaks the simple fixed convolution kernel across a sequence. Specialized scan algorithms and fused kernels recover efficient execution for suitable update forms. Do not infer that all recurrences can be parallelized equally well. Distinguish the algebraic dependency graph, the arithmetic count, and the amount of intermediate state an implementation materializes.

At autoregressive inference, a recurrent state may offer constant memory per layer with respect to context length. That does not mean constant total memory: model parameters, batch size, state width, and temporary buffers remain. Attention can retain explicit past keys and values, providing a different retrieval mechanism at a growing memory cost. Hybrid architectures combine these mechanisms because compressing a history and looking up a particular historical detail are different capabilities.

Evaluate both short and long contexts, including tasks requiring selective recall rather than only smooth signal prediction. Measure training throughput and token-generation latency separately; an implementation fast on long training sequences may have different decode behavior. Record hardware, state size, precision, and batch size. Check numerical stability over very long streams and whether resetting the state at document boundaries matches deployment. A theoretical asymptotic advantage is a hypothesis to test in a concrete regime.