State Space Models (SSM): Compressing Long Sequences with Controllable Dynamical Systems

A state space model compresses an ever-growing history into a fixed-dimensional state h. It does not need to reread the entire past each time it produces an output; instead, it lets the state evolve continuously with new inputs and treats the current state as a summary of historical information. In continuous time, this process is written as:

ḣ(t) = Ah(t) + Bx(t)

y(t) = Ch(t) + Dx(t)

Here, t denotes continuous time, x(t) is the input at time t, h(t) is the finite-dimensional summary of the history up to that time, ḣ(t) is the instantaneous rate of change of the state, and y(t) is the current output. The first equation answers “how the state changes next”: Ah(t) represents the way the old state itself persists or decays, and Bx(t) represents how the current input is written into the state. The second equation answers “how to obtain a visible output from the internal state”: Ch(t) reads out the information needed for the task from the state, while Dx(t) allows the current input to bypass the state and directly affect the output.

Therefore, A, B, C, and D respectively control state evolution, input writing, state readout, and input pass-through. Classical control systems use these matrices to describe physical dynamics; in sequence models, they are learned from data, allowing the finite-dimensional state to preserve as much task-relevant history as possible. The key trade-off here is: after the history is compressed, computation only needs to maintain h, but what the state can retain depends on these transformations and the state dimension.

Machine temperature monitoring in a discrete sequence can be written as hₜ = 0.8hₜ₋₁ + xₜ. hₜ₋₁ is the aggregate influence of previous temperature anomalies, the coefficient 0.8 means only 80% is retained at each step, and xₜ writes the new anomaly for the current day fully into the state. Given input x = [1, 0, 2] and initial state h₀ = 0, the model repeatedly performs “retain the old influence, then add the new input” in chronological order. Even if xₜ = 0 on a given day, the previously written influence does not disappear immediately, but remains in the state at a ratio of 0.8; when a new anomaly arrives, it again determines the current state together with the history that has not yet decayed. This example shows the core causal chain of state-space representations: the input changes the state, the state carries history, and the readout converts the state into the current output.

After sampling the continuous system at fixed intervals, the continuous-time state change must be converted into a one-step discrete-time recurrence:

hₖ = Āhₖ₋₁ + B̄xₖ

Here k is the discrete time step, xₖ is the input at step k, and hₖ₋₁ and hₖ are the states before and after the update, respectively. The overbars indicate that Ā and B̄ are not the original continuous-time matrices, but the one-step state-transition matrix and one-step input-writing matrix obtained after discretization. If the sampling step is Δ, then the state transition satisfies Ā = e^(ΔA). Here e denotes the natural exponential function, and e^(ΔA) is the matrix exponential, which converts the continuous evolution described by A into the cumulative change over one sampling interval. Discretization methods such as zero-order hold compute both Ā and B̄, so that the evolution of the old state and the effect of the input within the sampling interval use the same time scale.

Δ is part of the model's meaning. When the sampling interval changes, the real time corresponding to one step changes accordingly; therefore the original Ā and B̄ cannot always be reused. If the frequency changes without re-discretization, the same discretized step will represent a continuous evolution of different length, and the timescale expressed by the model will also change. Because the state transition is applied repeatedly, during learning it is also necessary to constrain the state dynamics, to prevent the numerical values from continually amplifying and exploding during the recurrence.

Taking the discretization result as the scalars Ā = 0.8 and B̄ = 1, and given x = [1, 0, 2], h₀ = 0, we can compute the state step by step:

In the first step there is no old state, so input 1 directly produces h₁ = 1. In the second step the current input is 0, so only 80% of the previous state is retained, giving h₂ = 0.8. In the third step, 0.8 first decays to 0.64, then the current input 2 is written, giving h₃ = 2.64. The final 2.64 is not produced by the latest input alone: the 2 comes from the current input, and 0.64 comes from memory left by past inputs after two consecutive state transitions. The discretized recurrence accumulates continually arriving inputs into a finite-dimensional state through this step-by-step updating.

A linear state-space model can be computed either by time recurrence or by writing the entire input as a one-dimensional convolution. The recurrent form updates the state step by step and is naturally suited to streaming processing, but each later step depends on the previous step, so directly unrolling in time is not easy to parallelize. To keep the convolution form below consistent with the general output equation in Section 1, two explicit assumptions are adopted here: omit the input feedthrough term, i.e., D = 0; and set the initial state before processing x₀ to h₋₁ = 0. Under these two assumptions, repeatedly substituting the recurrence eliminates the intermediate states, yielding the output at step k:

yₖ = Σᵢ₌₀…ₖ CĀⁱB̄ · xₖ₋ᵢ

If D ≠ 0, the complete output must also add the feedthrough contribution Dxₖ from the current input; if h₋₁ ≠ 0, it must also add the free response not produced by the input, CĀ^k+1h₋₁. The above expression is only the input convolution part retained when D = 0 and h₋₁ = 0, so index i = 0 then exactly corresponds to the writing of xₖ into the current state.

After defining Kᵢ = CĀⁱB̄, the same expression can be written as convolving the input sequence with a convolution kernel K. i represents the lookback distance: i = 0 corresponds to the current input, i = 1 corresponds to the previous input, and so on. xₖ₋ᵢ is the input from i steps ago; B̄ first writes it into the state; Āⁱ means this information undergoes i state transitions and thus propagates to the current time according to the system dynamics; C then reads the output from the propagated state contribution. Σ sums all contributions from the current position back to the earliest position to form yₖ.

The convolution kernel is not a set of free coefficients unrelated to the state model. The coefficient at every distance is generated by Kᵢ = CĀⁱB̄, so the entire set of long convolution kernels K shares the same state dynamics: the farther away the input is, the more times Ā is repeatedly applied, and how its influence is retained, decays, or changes is determined by Ā. Structured parameterization makes computing such a long kernel feasible without having to treat each distance completely independently.

These two expressions correspond to different computational needs. During inference, the current state h can be retained; each time a new input is received, only one state update and readout is performed, so relative to the length of history already processed, each step can perform an O(1) incremental update. During training, the complete sequence is usually already available, so a convolution kernel composed of Kᵢ can be constructed first and then the entire segment can be processed at once by parallel convolution or scan, to improve training throughput. Recurrence and convolution are not two different models, but two computational orders of the same linear system: use state recurrence when low-latency streaming processing is needed, and use the convolution or scan form when whole-segment parallel processing is needed.

A linear time-invariant state space model reuses the same set of A, B, and C at every position. “Time-invariant” means that the rules for state evolution, input writing, and state readout do not change with the content at the current position: a token representing a red marker and an ordinary word are subject to the same memory rules as long as they are at the same relative distance. The convolution kernel generated by this fixed dynamics also changes only with distance, making it difficult to directly express content-determined operations such as “remember strongly when encountering a red token, ignore when encountering other content.”

Selective SSM lets some state space parameters be generated dynamically from the current input:

Δₜ, Bₜ, Cₜ = fθ(xₜ)

hₜ = Ā(Δₜ)hₜ₋₁ + B̄ₜxₜ

xₜ is the input at the current position, and fθ is a small learnable function parameterized by θ. It reads xₜ and generates the step size Δₜ, write parameter Bₜ, and readout parameter Cₜ used at the current position. Δₜ determines how the continuous dynamics are discretized at the current step, yielding the state transition Ā(Δₜ); Bₜ corresponds to the discretized B̄ₜ and controls the extent to which the current input is written into the state; Cₜ controls which information in the current state is read out. hₜ₋₁ is the history saved before the update, and hₜ is the new state after selectively retaining the old state according to the current content and writing in xₜ.

This causal chain makes the model’s memory rules change with content: the current input first passes through fθ to generate parameters, and those parameters then control retention of the old state, writing of the current information, and readout of the result. Therefore, even if two inputs are at the same distance from the current output, the model can give them different degrees of retention because their content differs. For tasks such as “only remember red tokens,” a red marker can trigger stronger writing or more appropriate retention rules, while ordinary content can be weakened.

After parameters vary with position, there is no longer a set of simple convolution kernels fixed for all positions, so the long convolution computation of a linear time-invariant system cannot be directly reused. To still process the entire sequence efficiently, a hardware-friendly parallel scan is needed: it respects the recurrent dependency while batch-merging the computations of all steps. Selectivity thus enhances content-dependent memory, but does not remove the fundamental constraint of state compression; no matter how the parameters change, history is still summarized into a finite-dimensional state rather than saved completely item by item.

The state retention rate determines how quickly a single input fades after being written into the state. Suppose a pulse appears at a certain moment in the sequence, and there is no new input disturbance afterward; if at each step the previous state is multiplied by a fixed retention rate Ā, then after d steps the contribution of this pulse is Āᵈ. Each forward step multiplies by Ā again, so the farther the distance, the more accumulated multiplications.

Figure 1 compares the decay curves of the same pulse for Ā = 0.5 and Ā = 0.9. Both curves start from the early event, but 0.5 retains only half at each step and falls quickly; 0.9 retains ninety percent at each step and falls more gradually.

At a distance of 1 step, the two settings still retain 0.500 and 0.900, respectively. By step 5, the repeated multiplication by 0.5 has compressed the contribution to 0.031, while 0.9 still retains 0.590. By step 10, the former is only 0.001, and the latter is still 0.349; by step 50, the former is approximately 0, and the latter has also decayed to 0.005. Here the “effective memory length” is not the number of steps for which the event is fully preserved, but the range over which it still has a perceptible contribution to the current state: the flatter the curve, the earlier events can still influence positions farther away, and the longer the effective memory.

When Ā is fixed, all inputs follow the same decay curve. The selective mechanism can allow different inputs to correspond to different state retention scales: events that need to be stored for a long time use a slower decay, and short-term information uses a faster decay. The 0.5 and 0.9 in the figure therefore not only show two numerical settings, but also intuitively illustrate why content-dependent retention rules can change the memory span of different events. No matter how high the retention rate is, as long as it is less than 1, the contribution of a single pulse will still continue to decrease with distance; choosing a flatter curve prolongs the influence, rather than making a finite input never decay.

As sequence length n grows, SSM's asymptotic sequential computation is O(n), while attention's is O(n²). This shows that, with other conditions similar and n sufficiently large, SSM's computation grows linearly with length, while attention's pairwise position interactions grow faster. However, complexity only describes the growth trend and does not directly equal actual runtime on specific hardware.

At inference time, SSM compresses history into a fixed-dimensional state, so it does not need the state size to grow with sequence length n during continued generation; attention, on the other hand, retains KV for old positions, and its cache grows with n. This is an important difference in long-sequence resource requirements between the two. At the same time, attention can directly select a position among old KV, while SSM's access to old information must go through the compressed state, so their computation methods and information access capabilities are not the same.

Actual speed also depends on the constant cost of each computation step and whether the hardware can be fully utilized. SSM's linear advantage requires efficient scan and operator fusion to translate into throughput; although attention has the O(n²) growth term, it can leverage mature matrix operations and FlashAttention. For short sequences, the n² term is not yet large enough to dominate total time; constant costs such as kernel launches, data movement, and operator implementation may be more important. With small batches or lacking optimized kernels, hardware utilization may also be insufficient, so SSM with lower asymptotic complexity can still be slower.

Therefore, “O(n) is better than O(n²)” supports only the theoretical judgment as length grows and cannot replace deployment measurements. Whether it is actually superior must be determined on target hardware using the target sequence length and batch by actually comparing tokens/s, end-to-end latency, and memory usage. Only when these conditions are consistent do the measured results reflect the model's real efficiency on the specific workload.

State space models repeatedly apply the discrete state transition matrix Ā at each time step, so even a small amplification, decay, or numerical error can accumulate over a sufficiently long recurrence. Normal behavior within a training range of length 4k only shows that the dynamics and numerical errors are controllable within that range; extending the same recurrence to 100k steps may cause the state to gradually drift or even explode, and stability within the training range does not guarantee stability at arbitrary lengths.

The basic quantity for judging repeated transitions is the spectral radius of Ā, that is, the maximum of the absolute values of all its eigenvalues. It can be roughly understood as: when the state is repeatedly multiplied by Ā, whether the direction that is most easily amplified grows or decays. When the spectral radius is greater than 1, even a state component that is initially small may be continuously amplified over steps; when the spectral radius is far less than 1, historical influence decays rapidly and the model struggles to maintain long-range memory. Stability is therefore not simply pursuing "the smaller the better"; rather, it avoids amplification while preserving the time scales required by the task.

Deviations in long sequences do not come only from the idealized mathematical form. Finite precision introduces small rounding differences at each step, normalization changes the actual state evolution, and input-dependent step sizes make the transition rule vary with position. These factors may not be obvious on short sequences, but they gradually accumulate over many recurrent steps, so length extrapolation must be directly verified and cannot be inferred only from results within training lengths.

A length extrapolation curve can show whether performance gradually degrades beyond the training range; zero-input rollout isolates the state's own dynamics and can directly reveal drift or explosion that is not driven by new input; impulse response reveals the time scales over which different state components retain information; and precision switching exposes the recurrence's sensitivity to numerical representation. Only when these checks still appear trustworthy at the target length can stable behavior on short sequences be extrapolated to longer operating intervals.

Being able to process million-length inputs with acceptable computation and memory only shows that the model can let the sequence pass through the computation pipeline; it does not guarantee that any early token can still be retrieved exactly. SSM continuously compresses history into a fixed-dimensional state: this representation can summarize long-term trends and task-relevant signals, but may not be able to losslessly preserve many mutually unrelated details at the same time. The longer the sequence, the more information that must share the same finite state, and the more one should not conflate the ability to process length with the ability to recover specific content.

Tasks such as password copying, key-value association, needle-in-a-haystack, and those that require citing original text positions all put pressure on random access capability. Password copying requires the state to retain a segment of exact symbols; key-value association requires retrieving an old value paired with a particular key when a query appears; needle-in-a-haystack hides a target fragment in a large amount of distractor text and then requires the model to recover it; citing original text also requires returning the specific content at the corresponding position. Together, these tasks test not whether general trends have entered the state, but whether a piece of old information can be accurately located and read out at long distance and under strong interference.

Selective mechanisms can improve the write strategy, letting the model decide based on content which information should be saved with priority and which can be downweighted. But smarter selection has not turned the finite state into a database of infinite capacity: when many details may be queried arbitrarily in the future, the model still faces the information trade-off imposed by compression. Therefore, long context length itself is not proof of memory capability.

A clearly bounded combination is to let SSM handle local or streaming compression, efficiently summarizing constantly arriving information with a fixed state; when exact look-back is needed, sparse attention or external retrieval can then access specific historical content. The two parts separately take on summarization and exact access, avoiding requiring the finite state to preserve all original-text details by itself.

When evaluating long-sequence capability, three questions need to be distinguished: “Can the input fit?” measures whether the system can receive that length; “Is throughput scalable?” measures how the computational cost grows with length; “Can the information still be retrieved?” measures whether early details can be accurately recovered. Retrieval results should also be reported separately by target distance, number of distractors, and retrieval precision. Only when retrieval precision remains sufficient as distance increases and interference grows can the model be said to have corresponding long-range memory, not just long-sequence processing capacity.

SSM, RNN, convolution, and attention can all process sequences, but they differ in how they store history and access history. SSM and RNN share the core idea of recurrent state: at each step, read the current input and the previous state, generate a new state, and then produce output from the state. Therefore, when fixed-size state and streaming processing are needed, both can consume the sequence step by step without re-reading the entire history at each step.

Modern SSM is not merely giving old-style recurrence a new name. It starts from continuous dynamical systems, obtains sequence recurrence through discretization, and uses structured matrices and parallel scanning to improve training efficiency. The parameters of the continuous system describe how the state evolves over time; discretization converts this evolution into a transition at each sequence step; structured parameters make the computation of long-range dynamics feasible; and parallel scanning processes multiple positions in batches while preserving the recurrence dependencies. These mechanisms make SSM especially suitable for expressing very long, smooth dynamic changes.

When an SSM is a linear time-invariant system, the same set of state transition, write, and read parameters is reused at all positions. After unrolling the recurrence, the effect of each historical input on the current output is determined only by relative distance, so it is equivalent to a class of long convolutions generated by state dynamics. This shows that linear SSM and long convolution are not mutually exclusive models, but rather the recurrent form and the whole-sequence form of the same computational relationship. Ordinary convolution more directly matches local, translation-invariant patterns; structured SSM uses state dynamics to organize longer convolution kernels.

Selective SSM further makes the parameters depend on the input at the current position, so that different content triggers different write, retain, or read rules. At this point, positions no longer share a fixed set of convolution kernels, and the model goes beyond the limits of linear time-invariant long convolution. Attention takes another route: it explicitly retains representations of each position and addresses old positions according to the current content, so it is more suitable for tasks that require precise lookback at arbitrary positions; the costs and benefits cannot be summarized only by whether it is recurrent.

These correspondences describe the matching between mechanisms and requirements, not absolute model boundaries. When choosing, first determine whether the task requires continuous compression, long-timescale dynamics, local patterns, or precise content addressing of historical positions, and then choose the computational approach that more directly supports that requirement.

The recurrent state of an SSM is not a temporary cache that can be reused arbitrarily across requests. It is a compressed representation of previous inputs after successive updates, and it directly participates in the next step's output. As long as the state has not been reset, new input will interact with the residual history stored in it. Therefore, handing one user's state to the next user is equivalent to letting the latter's sequence continue to recur from a summary of the former's history, and the output will be affected by information that does not belong to the current session.

Deployment systems must bind state to explicit sessions and tenants. Every active sequence should acquire its own state, and after updates it should be saved back to the same identity. When the session ends, reset it explicitly; when it has not been used for a long time, reclaim it according to the timeout policy. State migration must also be handled when the model version changes, because old state is formed under the dynamics of the old model and cannot continue to be handed over to the new version without an explicit migration rule. The creation, ownership, update, reclamation, and migration of state together constitute its lifecycle.

Batch scheduling makes this requirement stricter. A batch may advance multiple sequences simultaneously, and each sequence's step t must connect to its own state from step t−1. Even if only one index or ordering mistake occurs, the wrong state will enter subsequent recurrence; new states are then generated from the wrong state, causing contamination to continue propagating rather than affecting only the one output at the moment of the mistake. The scheduler therefore must both compute in batch and keep sequence identity and state order consistently aligned.

Failure recovery likewise cannot treat “a state that still exists” as a usable state. The recovery process should rebuild session state from checkpoints with clear provenance and trusted content, and confirm that it corresponds to the correct session, model version, and sequence position. Old state with unclear provenance may contain incorrect history, misaligned results, or incompatible representations; silently reusing it will carry these problems into all subsequent outputs. Only when state ownership and provenance are verifiable is the continuity of recurrent inference trustworthy.

State space models begin with a clear question: how can a finite-dimensional state continuously carry history and produce the current output as the sequence keeps growing? Continuous dynamics first define how this state changes. The input x(t) enters the state h(t) through the write term, the state itself evolves according to the dynamics matrix, and the readout then converts h(t) into the output y(t). This layer describes the mechanism in ideal continuous time and gives the basic causal relationship of “input → state change → output”.

Real sequences consist of discrete positions, so the continuous dynamics need to be discretized according to a sampling step Δ. Discretization yields the one-step state transition Ā and the input write B̄, allowing the model to update according to hₜ = Āhₜ₋₁ + B̄xₜ. The sampling step determines how much continuous evolution one step represents, so when it changes, the corresponding discrete parameters must also change. The output of the discrete recurrence comes from the current state, and the current state is in turn formed by the old state and the new input together; history thus propagates step by step along the time axis.

The same linear time-invariant recurrence can be computed in a different order: after expanding the intermediate states, the effect of past inputs on the current output forms a long convolution kernel generated by the state dynamics. Streaming inference can retain the state and perform the recurrence step by step; training over the entire sequence can use convolution or parallel scanning. Both use the same system relationship; the difference lies in how the computation is organized, not in the meaning of the model.

Fixed parameters make inputs at the same distance follow the same memory rule. When it is necessary to decide by content “what to write, how long to retain, and what to read out,” selective parameters are generated from the current input, making the state update vary with content. This can enhance content selection capability, but history is still compressed into a finite state, and precisely storing a large number of mutually unrelated details still has limits. After parameters vary with position, the simple form of a fixed convolution kernel no longer applies, so a fused parallel scan is needed to achieve throughput that grows linearly with sequence length while respecting the recurrence dependencies.

Every design goal along this chain must be verified with corresponding evidence. Retrieval tests check whether compressed information can still be retrieved and should pay attention to target distance, number of distractors, and accuracy; length extrapolation checks whether repeated state transitions outside the training range decay reasonably, drift, or explode; hardware measurements compare tokens/s, latency, and memory at the target length, batch, and device to confirm whether linear complexity truly translates into deployment benefits. Only after the mechanism, information capacity, long-range stability, and actual efficiency have each been tested can one judge whether an SSM solves the target sequence problem.