betaFeedback

WorksComputer Science

Information Limits of Replay-Free Recurrent State Migration

Abstract

When a recurrent model is replaced, its old state may not determine what the new model would compute from the same history. We characterize the information that must be retained before the replacement is known. For a time-invariant affine linear family, the minimum continuous causal memory for order-kk local migration equals the reachable dimension of a lifted coefficient system minus the information in the anchor state. A controllable dd-state model with scalar input needs at most kdkd additional real coordinates, even when arbitrary matrix replacement directions are revealed only after streaming. A single rank-one direction can already require all kdkd. Conditional singular values and auxiliary-bit bounds distinguish this local information law from recovery at a fixed tolerance. We also give invariant-subspace and future-output constructions. Controlled experiments compare the resulting representations. In a small language model, equal-memory cubic interpolation improves mean state fidelity over third-order coefficients but provides no meaningful predictive gain. An analytic history basis preserves useful adaptation more economically in a coupled identification task. With repeated slow poles, eight history coordinates meet normalized output error 10−410^{-4} across five fitted seeds despite substantial full-state error. Splitting the poles raises the smallest tested successful width to 64.

Introduction

A recurrent model compresses a history under its current parameters. Replacing those parameters can change which historical distinctions matter. An expressive migration map cannot recover distinctions that the old state has discarded. We ask what information a processor must retain before the replacement is known to reconstruct the state that the new model would compute from the same inputs.

The target is retrospective. A query at time tt requests the state obtained by applying one replacement model to the complete prefix x1:tx_{1:t}, not the trajectory generated by historical weight changes. This question arises when a running filter is recalibrated or an existing recurrent context is reinterpreted. We study linear recurrent models with fixed input injections. Arbitrary changes to a multilayer network are outside this setting.

One relevant case is transition-only adaptation of a linear recurrent block, such as an LRU, with its input projection and upstream features frozen [17]. The general causal characterization permits vector inputs. The sharper kdkd bound additionally requires a controllable scalar-input anchor.

Our main result identifies the minimum continuous causal memory for local approximation of order kk. It equals the reachable dimension of a lifted coefficient system minus the information already present in the anchor state. For a controllable dd-state model with scalar input, the sharp worst-case bound is kdkd additional real coordinates. The encoder can be fixed before any matrix replacement direction is specified, while one rank-one direction can already require all kdkd coordinates. Unknown arbitrary directions and one suitably chosen direction therefore have the same worst-case local information cost. The result counts independent historical information, which can be smaller than the coefficient array that represents it.

Exact local order, finite-tolerance accuracy, and practical storage are distinct. We give conditional singular-value and auxiliary-bit bounds for a fixed finite query set, then construct causal coefficient memories under an invariant-subspace condition. An output quotient separates preservation of future predictions from preservation of every state coordinate. The experiments compare coefficient, interpolation, and history-basis representations at matched memory budgets and prescribed prediction tolerances. The memory-width study relates the required storage to the requested output and the anchor’s pole structure, with shared setup and decoder costs accounted for separately.

Relation to prior work. Recurrent-state staleness is studied by R2D2 (Kapturowski et al., [12]. RTRL propagates exact first derivatives Williams and Zipser [21], UORO approximates them online Tallec and Ollivier [19], and structured recurrent learning reduces their maintenance cost Farr et al. [5]. Expansion, invariant projection, rational realization, and residual estimation are established tools of parametric model reduction [2, 10]. Continuous nonlinear widths supply the fixed-horizon language [4, 18]. Laguerre models and HiPPO retain historical signals in prescribed bases [20, 8], whereas stitching transforms a representation using model-pair calibration [1, 14]. Context composition within an SSM [13] and state compression during training [3] concern different targets. The contribution is a causal information characterization for a replacement revealed after streaming. The differentiation rules, orthogonal filter families, and generic residual bounds are established ingredients. Appendix § 25 gives result-level comparisons.

Causal information before a replacement

Let ht(a)h_t(a) be the state produced from zero by processing x1:tx_{1:t} with the same coordinate aa. The anchor is ht(0)h_t(0). An auxiliary summary updates from its previous value, the anchor, and the current input without knowing future queries. A query returns an estimate of ht(a)h_t(a) but does not change the underlying summary. Queries at aa and then a′a' each concern the full prefix. They do not describe a trajectory that first used aa and then a′a'. After a deployment change, maintaining the anchor adds storage and computation to those of the active model.

Two histories already show why auxiliary information is necessary. The scalar old state is h2(0)=λx1+x2h_2(0)=\lambda x_1+x_2. Histories (x1,x2)(x_1,x_2) and (x1+v,x2−λv)(x_1+v,x_2-\lambda v) collide in that state, but replacing λ\lambda by λ+a\lambda+a separates their targets by avav. Retaining x1x_1 before the query resolves the ambiguity. Whether this distinction matters depends on the tolerance and readout.

The reachable coefficient space

Consider the time-invariant family

ht(a)=(A0+∑i=1paiAi)ht−1(a)+Bxt,h0(a)=0.(1)h_t(a)=\left(A_0+\sum_{i=1}^{p}a_iA_i\right)h_{t-1}(a)+Bx_t,\qquad h_0(a)=0. \tag*{(1)}

An auxiliary summary supports order-kk local migration when, for every finite history,

∥ht(a)−Da(ht(0),St)∥=O(∥a∥k+1)(a→0).(2)\lVert h_t(a)-D_a(h_t(0),S_t)\rVert=O(\lVert a\rVert^{k+1})\qquad(a\to0). \tag*{(2)}
QuestionResultEssential scope
Causal local order kkdim⁡Kk−dim⁡π0Kk\dim\mathcal{K}_k-\dim\pi_0\mathcal{K}_kFixed time-invariant affine family, real inputs
Directions revealed laterSharp worst-case kdkd extra coordinatesControllable scalar input, exact arithmetic
Fixed-horizon toleranceConditional singular values and a bit lower boundUnit-energy histories, finite queries, exact old state
Implementation costCoefficients, interpolation, or history banksMaintenance, conditioning, and predictive tolerance measured separately

Table 1. Four different memory questions. Local results count continuous real coordinates, not bits. All targets reprocess the same historical inputs under one replacement model.

The implied constant may depend on the history. The parameter set contains a neighborhood of zero. This definition concerns an asymptotic order, not a fixed-radius numerical error.

For two update directions, the first-order state and sensitivity coefficients obey

\begin{bmatrix} h_t^0 \\ z_{t,1} \\ z_{t,2} \end{bmatrix} = \begin{bmatrix} A_0 & 0 & 0 \\ A_1 & A_0 & 0 \\ A_2 & 0 & A_0 \end{bmatrix} \begin{bmatrix} h_{t-1}^0 \\ z_{t-1,1} \\ z_{t-1,2} \end{bmatrix} + \begin{bmatrix} Bx_t \\ 0 \\ 0 \end{bmatrix}. \tag*{(3)}\end{bmatrix}

The three blocks can contain redundant historical information. With d=2d=2 and scalar input, a controllable example has only four reachable coordinates in this six-coordinate array. Its anchor accounts for two, leaving two auxiliary coordinates rather than four. Appendix P.4 gives explicit noncommuting matrices, exact ranks through degree three, and a numerical realization.

Stack all coefficients of degrees zero through kk into jtj_t. Its exact recurrence is jt=Tkjt−1+Bkxtj_t=T_kj_{t-1}+B_kx_t, with A0A_0 on every diagonal block and AiA_i from block α−ei\alpha-e_i to block α\alpha. The input acts only on the constant block. Let nk=d(p+kk)n_k=d^{\binom{p+k}{k}}, let π0\pi_0 extract that block, and define the reachable coefficient space

Kk=∑s=0nk−1im⁡(TksBk).(4)\mathcal{K}_k=\sum_{s=0}^{n_k-1}\operatorname{im}\left(T_k^sB_k\right). \tag*{(4)}

Theorem 1 (Minimum causal local memory). For real-vector inputs, the minimum number of continuous causal auxiliary coordinates beyond the anchor that supports (2) at every finite horizon is

νk=dim⁡Kk−dim⁡(π0Kk).(5)\nu_k=\dim\mathcal{K}_k-\dim\left(\pi_0\mathcal{K}_k\right). \tag*{(5)}

A linear causal encoder attains this minimum, even when the competing decoders are unrestricted.

Histories that share a summary must agree in every coefficient through degree kk to satisfy local accuracy. The antipodal argument gives a lower bound once the coefficient system is fully reached. For the upper bound, choose a linear complement to π0\pi_0 on Kk\mathcal{K}_k, retain its coordinates, and update them before any query. Appendix H proves both directions. The minimum concerns exact local order, not numerical conditioning or update cost.

Theorem 2 (A rank-one direction can be worst case). For every d,k≥1d,k\ge1, a uniformly contractive scalar-input family

hs(a)=(A+avvT)hs−1(a)+bus(6)h_s(a)=(A+avv^\mathsf{T})h_{s-1}(a)+bu_s \tag*{(6)}

requires kdkd additional continuous coordinates for (2) at horizon d(k+1)d(k+1). Retaining its first kk coefficient vectors attains this count.

Choose AA diagonal with distinct eigenvalues in (0,1)(0,1) and all entries of v,bv,b nonzero. Its coefficient lift has AA on each diagonal block and vvTvv^{\mathsf{T}} immediately below. Controllability makes its d(k+1)d(k+1) coordinates independent functions of a sufficiently long history. The anchor retains only dd. Appendix § 12 proves this by the PBH criterion. This is an existence result, not a claim about every rank-one family.

The same kdkd bound suffices for a scalar-input model permitting arbitrary transition replacements.

Corollary 3 (Sharp direction-independent scalar-input memory). If (A0,b)(A_0,b) is controllable and xtx_t is scalar, kdkd auxiliary real coordinates suffice for order-kk local migration under every matrix replacement A0+ΔA_0+\Delta. The causal encoder can be chosen from (A0,b,k)(A_0,b,k) before Δ\Delta or any update directions are known. No smaller worst-case count is possible. In particular, for every finite affine family, νk≤kd\nu_k \le kd, independently of pp.

Let PP be the characteristic polynomial of A0A_0. The matrix P(Tk)P(T_k) strictly increases coefficient degree, so P(Tk)k+1=0P(T_k)^{k+1}=0. A scalar input can therefore reach at most d(k+1)d(k+1) lifted dimensions, regardless of the number of monomials. Subtracting the controllable anchor gives kdkd.

To construct a direction-independent encoder, put p(z)=det⁡(I−zA0)p(z)=\det(I-zA_0) and J(z)=adj⁡(I−zA0)J(z)=\operatorname{adj}(I-zA_0). The order-kk response to Δ\Delta has transfer function

Hk(z,Δ)=∑ℓ=0k[J(z)zΔ]ℓJ(z)b p(z)k−ℓp(z)k+1.(7)H_k(z,\Delta)=\frac{\sum_{\ell=0}^{k}[J(z)z\Delta]^\ell J(z)b\,p(z)^{k-\ell}}{p(z)^{k+1}}. \tag*{(7)}

Its numerator degree is less than d(k+1)d(k+1) and its denominator is independent of Δ\Delta. One scalar filter therefore supports all replacement directions. A coordinate transformation incorporates the ordinary anchor and leaves kdkd auxiliary coordinates. Appendix § 21 proves the construction and truncation bound and discusses conditioning. The information result assumes exact arithmetic. It does not justify using a high-degree companion filter in a large model; a smaller declared family can reduce implementation cost.

Fixed-horizon tolerance and precision

Throughout, vector and operator norms are Euclidean. The continuous lower bounds apply to real histories and need not extend to finite-alphabet tokens. For a fixed horizon, write the old state as R0uR_0u, with u∈B2nu\in B_2^n, and stack the target maps into RuRu. Let P0=I−R0TR0P_0=I-R_0^{\mathsf{T}}R_0. The auxiliary encoder S:B2n→RmS:B_2^n\to\mathbb{R}^m must be continuous. This excludes discontinuous infinite-precision encodings of an entire history into one real. The decoder need not be continuous.

Theorem 4 (State side information). With singular-value lists extended by zeros,

inf⁡S continuous,D sup⁡∥u∥≤1∥Ru−D(R0u,S(u))∥=σm+1(RP0).(8)\inf_{S\ \mathrm{continuous},D}\ \sup_{\lVert u\rVert\le1}\lVert Ru-D(R_0u,S(u))\rVert=\sigma_{m+1}(RP_0). \tag*{(8)}

In particular, exact recovery requires and is attained by

rank⁡[R0R]−rank⁡R0(9)\operatorname{rank}\begin{bmatrix}R_0\\R\end{bmatrix}-\operatorname{rank}R_0 \tag*{(9)}

additional coordinates at that horizon.

The old state supplies R(I−P0)uR(I-P_0)u. Leading right-singular coordinates recover the remaining component optimally. For the lower bound, Borsuk–Ulam on a sphere in ker⁡R0\ker R_0 gives indistinguishable antipodal histories with separated targets. This is a specialization of classical width arguments, not a new topological method. Appendix § 11 gives the full proof. The attaining sketch need not admit an inexpensive causal update.

Normalize a finite query set by RQ=J−1/2[R1⊤,…,RJ⊤]⊤R_Q=J^{-1/2}[R_1^\top,\ldots,R_J^\top]^\top. Its Euclidean error is RMS error over the JJ queries. The next statement turns exact rank into an accuracy requirement.

Theorem 5 (Tolerance and auxiliary bits). For ϵ>0\epsilon>0, the minimum continuous auxiliary dimension for worst-history RMS error at most ϵ\epsilon is

mϵ=#{i:σi(RQP0)>ϵ}.(10)m_\epsilon=\#\{i:\sigma_i(R_QP_0)>\epsilon\}. \tag*{(10)}

If instead the auxiliary message has at most 2b2^b values, even a discontinuous encoder requires

b≥∑ilog⁡2+(σi(RQP0)ϵ).(11)b\geq\sum_i\log_2^+\left(\frac{\sigma_i(R_QP_0)}{\epsilon}\right). \tag*{(11)}

The old state is supplied exactly in both statements.

The bit bound follows by covering the conditional target ellipsoid with 2b2^b radius-ϵ\epsilon balls. Appendix § 19 gives the proof and an explicit quantized upper bound. Per-query error ϵ\epsilon implies the RMS condition, but the converse need not hold. Neither statement identifies a finite-bit, causal optimum over a continuum of queries.

Exact recovery can be much more demanding. A contractive scalar recurrence hs(a)=(λ+a)hs−1(a)+ush_s(a)=(\lambda+a)h_{s-1}(a)+u_s can require t−1t-1 extra coordinates to recover every allowed target exactly. Evaluations at tt distinct parameters recover the entire history through a Vandermonde system (Proposition 9). Small conditional singular values can nevertheless make far fewer coordinates sufficient at a nonzero tolerance.

Structured memory and output preservation

For time-invariant matrices the smallest A0A_0-invariant space containing the update images is

References

  1. [1]Yamini Bansal, Preetum Nakkiran, and Boaz Barak. Revisiting model stitching to compare neural representations. In Advances in Neural Information Processing Systems, volume 34, pages 225–236, 2021. URL https://proceedings.neurips.cc/paper/2021/hash/01ded4259d101feb739b06c399e9cd9c-Abstract.html.arxiv.org/abs/2106.07682
  2. [2]Peter Benner, Serkan Gugercin, and Karen Willcox. A survey of projection-based model reduction methods for parametric dynamical systems. SIAM Review, 57(4):483–531, 2015. doi: 10.1137/130932715.DOI
  3. [3]Makram Chahine, Philipp Nazari, Daniela Rus, and T. Konstantin Rusch. The curious case of in-training compression of state space models. In International Conference on Learning Representations, 2026. URL https://arxiv.org/abs/2510.02823.
  4. [4]Ronald A. DeVore, Ralph Howard, and Charles Micchelli. Optimal nonlinear approximation. Manuscripta Mathematica, 63:469–478, 1989. doi: 10.1007/BF01171759.DOI
  5. [5]Noah Farr, Aryaman Reddi, Carlo D’Eramo, and Jan Peters. Streaming reinforcement learning under partial observability with real-time recurrent learning. arXiv:2605.24709, 2026. URL https://arxiv.org/abs/2605.24709.
  6. [7]Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. In Conference on Language Modeling, 2024. URL https://arxiv.org/abs/2312.00752.
  7. [8]Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. HiPPO: Recurrent memory with optimal polynomial projections. In Advances in Neural Information Processing Systems, volume 33, 2020. URL https://arxiv.org/abs/2008.07669.
  8. [9]Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2022. URL https://arxiv.org/abs/2111.00396.
  9. [10]Bernard Haasdonk and Mario Ohlberger. Efficient reduced models and a posteriori error estimation for parametrized dynamical systems by offline/online decomposition. Mathematical and Computer Modelling of Dynamical Systems, 17(2):145–161, 2011. doi: 10.1080/13873954.2010.514703.DOI
  10. [11]Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022. URL https://arxiv.org/abs/2106.09685.
  11. [12]Steven Kapturowski, Georg Ostrovski, John Quan, Rémi Munos, and Will Dabney. Recurrent experience replay in distributed reinforcement learning. In International Conference on Learning Representations, 2019. URL https://willdabney.com/publication/r2d2/.
  12. [13]Tian Yu Liu, Alessandro Achille, Matthew Trager, Aditya Golatkar, Luca Zancato, and Stefano Soatto. PICASSO: Permutation-invariant context composition with state space models. In International Conference on Learning Representations, 2025. URL https://arxiv.org/abs/2502.17605.
  13. [14]Zheda Mai, Ke Zhang, Fu-En Wang, Zixiao Ken Wang, Albert Y. C. Chen, Lu Xia, Min Sun, Wei-Lun Chao, and Cheng-Hao Kuo. Revisiting model stitching in the foundation model era. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2026. URL https://arxiv.org/abs/2603.12433.
  14. [15]Jiří Matoušek. Using the Borsuk–Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. Springer, 2003. doi: 10.1007/978-3-540-76649-0.
  15. [16]John Miller and Moritz Hardt. Stable recurrent models. In International Conference on Learning Representations, 2019. URL https://arxiv.org/abs/1805.10369.
  16. [17]Antonio Orvieto, Samuel L. Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 26670–26698, 2023. URL https://proceedings.mlr.press/v202/orvieto23a.html.arxiv.org/abs/2303.06349
  17. [18]Jonathan W. Siegel. Sharp lower bounds on the manifold widths of Sobolev and Besov spaces. Journal of Complexity, 85:101884, 2024. doi: 10.1016/j.jco.2024.101884. URL https://arxiv.org/abs/2402.04407.
  18. [19]Corentin Tallec and Yann Ollivier. Unbiased online recurrent optimization. In International Conference on Learning Representations, 2018. URL https://arxiv.org/abs/1702.05043.
  19. [20]Bo Wahlberg. System identification using Laguerre models. IEEE Transactions on Automatic Control, 36(5):551–562, 1991. doi: 10.1109/9.76361.
  20. [21]Ronald J. Williams and David Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural Computation, 1(2):270–280, 1989. doi: 10.1162/neco.1989.1.2.270.DOI

Paper details

vlnc:W_d7mv3vs2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Generative AI

View statement
Looking for related papers…
Contents