Approximate Memory Suffices for Universal Approximation with State Space Models

Sequence models in machine learning compress long input histories into finite-dimensional states, from recurrent networks and reservoir computing to recent state space models for long-context data. This raises a basic expressivity question: how simple can the recurrent memory be before it can no longer approximate stable causal sequence-to-sequence maps? We answer this question for fading-memory operators, where the distant past has uniformly diminishing influence. We show that every continuous causal time-equivariant fading-memory operator on a compact input set can be uniformly approximated by a state space model whose recurrence is a fixed diagonal linear contraction. The dynamics are time-invariant, input-independent, and contain no nonlinear hidden-state update or delay-line structure. The construction uses a bank of short exponential traces; although such traces do not exactly store a recent input window, a singular Vandermonde extraction approximately reconstructs the window while the remaining tail becomes negligible as delta decreases. We also prove that exact delay recovery is impossible for any fixed finite trace bank, showing that the accuracy-dependent extraction is essential. Technically, the result separates recurrent expressivity from exact memory storage, while exposing a conditioning cost in the readout. More broadly, it clarifies why highly stable, structurally simple SSM cores can still be universal approximators for stable sequence behavior.