acceptodds
Under review as a conference paper at ICLR 2027

The Cost of Long Memory: State, Context, and Stability Complexity in Sequence Models

Abstract

Long-range temporal dependence poses a resource question for sequence models: for a specified predictive-memory law, how much state, context, or dynamical criticality is required in order to forecast accurately? We study this question directly in forecasting risk. For algebraically decaying predictive memory, we prove matching upper and lower approximation bounds for exponential and finite-state modes. The best -mode forecast error decays as , so reaching forecast error needs states or modes. Earlier curse-of-memory results establish broad limitations of stable recurrent models under different approximation notions; here both sides match for one canonical predictive target in forecast risk, which fixes the optimal resource exponent for that target. We then show that genuine fractional long memory changes the geometry itself. In particular, forecast error is measured after fractional integration, prediction from a finite context of length has an exact leading order, and a fixed fractional strength keeps the square-log state-complexity law. Near the short-memory boundary, we identify the relevant and scales and give a uniform constructive law in the intermediate regime. For nonlinear contextual recurrences with uniformly contractive state dynamics, we derive an exponential first-chaos envelope and an explicit necessary condition that relates forecast accuracy to the contraction margin. Vanishing forecasting error on an algebraic target forces the recurrence quantitatively toward criticality, a condition that is necessary and not by itself sufficient. Finite-sample Kullback–Leibler calculations further connect the predictive geometry to statistical information. Theorem-matched experiments with contractive state-space, gated recurrent, and attention models reproduce the state and stability predictions. Matched exponential-memory controls locate the floor in the compatibility between the target tail and the contraction margin rather than in algebraic decay as a functional form, since an exponential target matched to the contraction is fit almost exactly.

Primary area:
learning on time series and dynamical systems
Keywords:
long-range dependence, state-space models, approximation theory, recurrent neural networks, time-series forecasting

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_94UdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies the resources required for accurate forecasting when the target process has slowly decaying predictive memory. The authors investigate three resources: the dimension of a linear recurrent state, the available context length, and the contraction margin of recurrent dynamics.

The main contribution is a matching upper and lower bound on the approximation error of finite-dimensional linear-state models for algebraically decaying predictive-memory kernels. Further results characterize finite-context prediction for fractional long-memory processes and establish a necessary relationship between forecasting accuracy and the contraction margin of nonlinear recurrent models. Numerical calculations and synthetic experiments illustrate these findings.

Critical strengths

S1. A useful formulation of memory complexity. Framing memory as a target-specific predictive law and measuring the resources required to approximate it in forecast risk is theoretically appealing. This provides a more precise perspective than qualitative discussions of long-memory capabilities.

S2. Matching state-complexity bounds. Theorem 1 is the strongest contribution. The matching root-exponential upper and lower bounds establish a precise relationship between state dimension and forecasting accuracy for the considered target and architecture class. The mathematical analysis is detailed, and the authors generally acknowledge the limitations of their results.

Critical weaknesses

W1. The theoretical scope is considerably narrower than the framing suggests. The title and abstract suggest results about long memory in sequence models broadly, whereas the main state-complexity theorem concerns linear-state approximations of a specific predictive-memory law. The nonlinear result requires uniform contraction and bounded derivatives, excluding many modern architectures and noncontractive recurrent dynamics. These restrictions are mathematically reasonable, but considerably limit the generality of the conclusions. The paper would benefit from a narrower title and a clearer statement of which sequence-model classes its results actually characterize.

W2. The framework does not address important nonlinear mechanisms of temporal dependence. The analysis focuses on linear predictive-memory kernels and, for the nonlinear recurrence result, uniformly contractive dynamics. However, nonlinear dynamical systems can exhibit long-range temporal dependencies through oscillations, multistability, or chaotic dynamics. Such dependencies need not correspond to a slowly decaying linear prediction kernel, and a model that reconstructs the underlying low-dimensional dynamics may have very different state-complexity requirements. Although the authors acknowledge some architectural limitations, the distinction between approximating a linear predictive-memory law and representing memory generated by nonlinear dynamics deserves substantially more attention. This is important for understanding the relevance of the results to time-series modeling beyond the considered setting.

W3. Important connections to existing literature are missing. The related-work discussion focuses heavily on recent state-space architectures and curse-of-memory results, while giving limited attention to established work on memory in recurrent dynamical systems. Particularly relevant are earlier studies on memory capacity in recurrent networks (Jaeger, 2002; White et al., 2004; Ganguli et al., 2008; Dambre et al., 2012), which investigate how dynamical systems store past inputs and how memory capacity relates to state dimension. The work of Miller and Hardt (2019) on stable recurrent models is especially relevant to the relationship between contraction and effective context length. Furthermore, studies on computation near the edge of chaos (Bertschinger and Natschläger, 2004; Legenstein and Maass, 2007) provide a broader dynamical perspective on the role of stability. Although these works do not establish the same target-specific forecast-risk bounds, a more thorough discussion would help clarify the paper's novelty and situate its results within the established literature on recurrent memory and dynamical systems. These works do not necessarily establish the same forecast-risk bounds, but they provide important context for the relationship between memory, state dimension, and dynamical stability.

W4. The experiments are too limited to establish the broader relevance of the theoretical results. Figure 1 mainly visualizes quantities derived from the theoretical analysis rather than evaluating learned models. Figure 2 uses a small synthetic benchmark with noiseless linear targets, context length 64, and relatively small architectures. Furthermore, the stability sweep only provides qualitative evidence: the derivative bounds can change with the contraction factor, and at larger contraction factors the effective memory timescale exceeds the available context. Thus, the experiment does not directly validate the quantitative asymptotic relationship in Corollary 7. While the matched exponential controls are useful, the experiments provide limited evidence about the behavior of modern sequence models on realistic forecasting problems. Evaluation on noisy observations or nonlinear data-generating processes would significantly strengthen the paper.

W5. The manuscript requires a substantial rewrite to improve clarity and presentation. The manuscript is difficult to follow despite careful reading. In particular, the experiments section discusses results without first adequately introducing the prediction task, models, and experimental procedure. Essential information is deferred to Appendix G, forcing readers to repeatedly move between the main text, figures, and appendix to understand what was actually done. The presentation also suffers from considerable repetition, particularly in comparisons with existing curse-of-memory results and repeated qualifications of the theoretical claims. I strongly recommend a substantial rewrite rather. The authors should introduce the experimental setup clearly in the main text, explain the figures systematically, reduce repetition, and use the resulting space to better motivate and contextualize the theoretical contributions.

Questions for authors
  1. How would the proposed framework extend to nonlinear data-generating systems or recurrent models with noncontractive dynamics? Could memory arising from low-dimensional oscillatory or chaotic dynamics lead to fundamentally different relationships between state dimension and forecasting accuracy? And how would one even approach this setting?

  2. Corollary 7 establishes that accurate approximation of algebraic memory requires the contraction margin to approach zero. Could the authors relate this limit to slow modes or nearly neutral directions in dynamical systems? How does their notion of near-criticality relate to established dynamical-systems perspectives? I would assume their finding basically relates to the idea that forcing systems to approach line attractor types of dynamics which naturally helps them store memory.

  3. Which of the observed error floors would the authors expect to persist for noisy forecasting tasks or nonlinear data-generating processes? Can the authors provide empirical evidence supporting these expectations?

4 comments

We thank the reviewer for a detailed and constructive review. We take the points in order.

W1, scope and title. We agree that the title is broader than the results. For the camera-ready version we will use "The Cost of Long Memory: Sharp State, Context, and Stability Laws for Algebraic Predictive Memory". Table R9 in App. H.1 states, architecture by architecture, which result applies and under which condition. In short, LTI state-space layers are covered by Theorem 1, and by Corollary 7 when their transition has operator norm below one. Selective layers that are affine in the state, such as Mamba, GLA and Gated DeltaNet, are covered by Corollary 7 when their transition norm stays below ρ\rho for every input and their injection is bounded. Proposition R2 extends this to fixed-depth stacks with Lipschitz maps between layers. Noncontractive recurrences such as unitary or oscillatory models have margin zero and face no stability obstruction, and the table says so.

W2 and Q1, nonlinear mechanisms. The scope of the paper is the linear predictive law, that is, the first Wiener chaos, or the Wold representation for Gaussian processes. Three examples show how this scope separates from nonlinear predictability.

  • The logistic map xt+1=4xt(1−xt)x_{t+1}=4x_t(1-x_t) in its stationary law has uncorrelated centred values, so its linear memory is zero, yet a one-dimensional state predicts it perfectly.
  • Alternating renewal processes with heavy-tailed durations have algebraically decaying autocovariance, which is classical. Their Bayes predictor needs only the current regime and its age, and the age is a counter with Jacobian one, so it is noncontractive and falls outside the hypotheses of Theorem 6.
  • Low-dimensional linear oscillations have a rational transfer function, hence finite Hankel rank by Kronecker's theorem, and a finite number of modes represents them exactly. The square-log law is thus a signature of scale-free memory, and oscillation alone does not trigger it.

A natural way forward replaces the Hankel rank by the dimension of a minimal predictive state. For Gaussian processes this is the number of nonzero canonical correlations between past and future, as in Akaike's stochastic realization theory, and in the nonlinear case it corresponds to causal states. Lower bounds would then need a chaos-by-chaos analysis, which we leave open, and the Discussion now says so. The new experiment with a nonlinear target (App. G.17, Table R8) shows the first-chaos part of the floor persisting while nonlinear models capture the higher chaoses.

W3, related work. Sec. 1.1 and App. H.2 now discuss Jaeger (2002) and White, Lee and Sompolinsky (2004) on memory capacity, Ganguli, Huh and Sompolinsky (2008) on the Fisher memory curve, Dambre et al. (2012) on information processing capacity, Bertschinger and Natschläger (2004) and Legenstein and Maass (2007) on the edge of chaos, Miller and Hardt (2019) on stable recurrent models, and Orvieto et al. (2023) on LRU. The bound MC≤NMC\le N and, for Gaussian inputs, the Hermite version of the capacity decomposition are trace-level and Wiener-chaos counterparts of our rank and first-chaos objects, and our results add the full error curve for a fixed target. On Miller and Hardt we agree that the mechanism is the same. App. D.13 shows that under Lipschitz budgets an L2L_2 version of their truncation argument, combined with the tail of the target beyond the truncation length, gives the rate of Corollary 7, and Sec. 5.1 now says that this part is classical. What Theorem 6 adds is a bound on each lag separately, which Figure 2(a) measures, and Proposition R1 shows that the resulting rate is sharp up to a logarithm.

W4, experiments. We agree that the L=64L=64 sweep could not test Corollary 7, and the revision explains why. At L=64L=64 the class optimum is already 4×10−64\times10^{-6} at ρ=0.95\rho=0.95 and below 10−2110^{-21} for ρ≥0.99\rho\ge0.99, so no stability floor is left to measure. The new experiments address each of your points.

  • Context. Trained sweeps at L=1024L=1024 and L=4096L=4096. At L=4096L=4096 the crossing lag satisfies J≤L/4J\le L/4 for every ρ≤0.99\rho\le0.99, so these points probe the asymptotic regime.
  • Derivative bounds that change with ρ\rho. Proposition R2 shows that budgets growing like δ−p\delta^{-p} leave the exponent of Corollary 7 unchanged. The gated cell has p=1p=1, so its stability sweep is now covered by the corollary.
  • Quantitative test. We compute the exact class optimum and place it between the bound of Lemma 30 and the construction of Proposition R1 (Table R1, Figure R2). Trained SSMs at L=4096L=4096 reach 1.00 to 1.67 times this optimum, and refitting only their readout brings them within 3% of it, so the learned eigenvalues are close to optimal (Table R4).
  • Noisy and nonlinear settings. Forecasting FARIMA(0,d,0) from its own observations, and a target that is nonlinear in the input (see Q3).

The gated cell stays above its own bound at all margins, and for ρ≥0.98\rho\ge0.98 it levels off between 2.3×10−32.3\times10^{-3} and 3.1×10−33.1\times10^{-3}, with width giving almost no gain. We report this as a limit of the optimization or parameterization of that cell (App. G.14).

W5, presentation. In the revised PDF the main text gains Figure R1 with a paragraph that summarizes the new tests, repetition of the curse-of-memory comparison is removed, and a roadmap opens the appendix. For the camera-ready version we will move App. G.1 to G.4 into Sec. 7 so that the task, models and protocol come before the results, and use the space this frees to motivate the theorems.

Q2, near-criticality and slow modes. A single neutral mode gives a constant kernel and leaves an error of order one on a decaying target. What Corollary 7 and Proposition R1 call for is a ladder of slow modes whose decay rates spread log-uniformly over [δ,O(1)][\delta, O(1)], with the slowest rate of order τ1/(2α−1)\tau^{1/(2\alpha-1)} up to a logarithm and about log⁡2(1/τ)\log^2(1/\tau) modes in total. Accuracy thus pushes the dynamics toward a continuum of slow directions, a graded version of a line attractor. The active nodes of the class optimum have exactly this layout (Figure R2(b)). In training the layout matters, because most decay rates stay close to their initial values. From a log-uniform initialization training changes each rate by a median factor of 1.1 and by at most 1.6 at ρ=0.99\rho=0.99, and the learned eigenvalues end close to optimal, with readout refit within 3% of the optimum. From rates near one only two to four of the 64 rates travel down to the slow range, and the refit stays 1.4 to 2.5 times above the optimum for 0.95≤ρ≤0.990.95\le\rho\le0.99 (Table R4, App. G.14). This layout matches the log-uniform step-size initialization of S4D and is related to the ring initialization of LRU, whose radii are set close to one for long-range tasks. One more link to dynamical systems is a non-normal delay line with unit gain, of the kind studied by Ganguli et al. (2008). It has spectral radius zero and operator norm one, so its margin is zero, which is why Theorem 6 is stated in operator norm.

Q3, noisy and nonlinear data. Theory first: when a uniformly contractive recurrence reads a Gaussian observed process, the linear part of its forecast has coefficients bounded by the same envelope, up to a restart error that decays like ρk\rho^k (Proposition R7), so the floor of Corollary 7 persists for forecasting from observations with a regular spectrum. For FARIMA(0,d,0) a truncation argument gives the floor σ2d2δ/{16log⁡(e/δ)}\sigma^2d^2\delta/\{16\log(e/\delta)\} (Proposition R8). This floor has exponent 1, where the coefficient tail alone gives only 1+2d1+2d. The bound behind it, equation (R1), holds at every margin, and the exact class optimum stays within a factor 1.7 to 1.9 of it for 0.003≤δ≤0.70.003\le\delta\le0.7. Then numerical evidence: the exact class optimum for FARIMA has local slope 1.08 to 1.14 in δ\delta for d=0.25d=0.25 and d=0.4d=0.4, close to 1 and far from 1.5 and 1.8 (Table R3). Trained SSMs that forecast one exact FARIMA path of length 2202^{20} stay above this optimum, at 1.11 to 4.52 times it for d=0.4d=0.4, and their readout refit is within 7% (Table R7). For the nonlinear target y=tanh⁡(s)y=\tanh(s) every model keeps a first-chaos mismatch above the class optimum for the first-chaos kernel, while the tanh RNN lowers its total error below the linear limit through higher chaoses (Table R8). The results need Gaussian inputs, and we do not prove a matching upper bound for the fractional floor.

We would be grateful if you could let us know whether these changes address your concerns, in particular W4 and Q3.

Reviewer_94UdOpenReview ↗

Update on review

I would like to thank the authors for their detailed responses and for the considerable additional work they have put into the revision. I think they have addressed many of my comments very well, and the manuscript has improved substantially.

On the one hand, I think this is an original and theoretically interesting contribution, and I certainly see the value of establishing rigorous bounds in this setting. On the other hand, I still have some reservations about the scope of the work and how broadly the results apply.

In particular, although the analysis also considers nonlinear recurrent models, the stability results rely on uniform contraction, and the framework is still largely concerned with linear predictive memory. This leaves out important nonlinear dynamical mechanisms, such as multistability or chaos, which I think are particularly relevant for many real-world systems. The authors now discuss these limitations and suggest possible directions to extend their framework, which I appreciate. However, these extensions seem far from straightforward and would likely require quite different theoretical approaches.

I therefore still find it difficult to judge how much the results tell us about memory in more general nonlinear state-space models, especially when the temporal dependencies arise from the underlying nonlinear dynamics rather than from a linear memory kernel. And I believe this crucial for this conference.

For these reasons, I have decided to keep my original score. I do want to emphasize, however, that I see clear merit in this work, and that I really appreciate the effort the authors have made to address my concerns.

Thank you for the follow-up and for reading the revision so closely. We are glad that the changes addressed many of your comments, and we agree with your description of where the results stop. The stability law needs uniform contraction, the lower bounds concern the linear part of the forecast, and multistable or chaotic models lie outside both. Extending the bounds to them will need different tools. Two points on what the results already say about nonlinear dynamics may still help in judging the scope.

Data generated by nonlinear dynamics. The lower bound of Corollary 7 does not need the data to come from a linear kernel. The argument of Theorem 6 applies to any target that is a square-integrable function of past Gaussian inputs, for instance, the output of a nonlinear system driven by them, with a model that reads the same inputs. The linear part of such a target has coefficients E[ytZt+1−j]\mathbb{E}[y_tZ_{t+1-j}], the covariances between the target and past inputs, and the risk of any forecaster is at least its error on this part. So whenever nonlinear dynamics leave an algebraically decaying trace in these covariances and whatever mechanism produced the data, every uniformly contractive model pays the stability cost of Corollary 7. App. G.17 checks this for the target tanh⁡(s)\tanh(s), where every trained model keeps its first-chaos error above the class optimum. Mechanisms that leave no such trace, like the logistic map in our earlier reply, are invisible to these bounds, and there we agree that new tools are needed.

When multistability or chaos becomes necessary. Uniform contraction rules out multistability and chaos by definition, since a contracting recurrence forgets its initial state and settles on a single trajectory for each input sequence. For tanh networks, ∣∣W∣∣≤ρ<1||W||\le\rho<1 is enough, which is the usual sufficient condition for the echo state property. Corollary 7 and Proposition R2 measure what this class can reach. At margin δ\delta, with budgets that grow at most polynomially in 1/δ1/\delta, the risk on an algebraic target is at least of order δ2α−1\delta^{2\alpha-1} up to a logarithm. A model with such budgets that does better must give up uniform contraction at that margin somewhere on its state space, through slow or neutral directions, several attractors, or expanding directions. Proposition R1 shows that shrinking the margin with a ladder of slow linear modes is enough. Whether multistable or chaotic models can reach the same accuracy with fewer states than Theorem 1 requires of linear models is open, and we find it a good question for future work.

Relevance for ICLR. We agree that nonlinear dynamics matter for many real systems. The recurrent layers that are widely used for long sequences, such as S4D, LRU and Mamba, are built to be stable, and each of their steps contracts a diagonal state. Table R9 states when this contraction is uniform. For these layers the paper gives the state, context and margin costs of algebraic memory, and trained SSMs come within a factor 1.7 of the class optimum (Table R4). In the camera-ready version we will add the two points above to the Discussion and name multistable and chaotic dynamics as the main open case.

We respect your decision to keep the score, and we thank you again for the careful review and for engaging with the revision in such detail.

Reviewer_5UsZOpenReview ↗
Rating
2
Confidence
1(−1)
Informativeness
1(−1)
Presentation
1(−1)
Soundness
2
Read review
Paper summary

This paper studies the state, context, and stability requirements of long-range predictive memory in sequence models. It establishes matching root-exponential approximation bounds for algebraic memory, yielding a state-complexity law of r∗(τ)=Θ(log⁡2(1/τ))r^*(\tau) = \Theta(\log^2(1/\tau)). For fractional long-memory processes, it characterizes the forecast-risk geometry and derives a sharp 1/L1/L finite-context prediction law. It also establishes a necessary relationship between forecasting accuracy and the contraction margin of nonlinear recurrent models. Additional results connect forecast risk to Gaussian KL divergence and finite-sample information.

Critical strengths

The main strength of the paper is Theorem 1, which establishes matching upper and lower bounds on the excess forecasting risk when approximating an algebraically decaying predictive-memory kernel with finite-dimensional linear-state models. The resulting state-complexity law, (r∗(τ)=Θ(log⁡2(1/τ))r^*(\tau) = \Theta(\log^2(1/\tau))), characterizes how the required state dimension scales with the target prediction accuracy. Although the analysis builds on classical exponential-sum approximation and Hankel spectral theory, establishing matching bounds for the specified forecasting setting provides a concrete theoretical result.

Critical weaknesses

Several central ingredients are closely related to established results. The exponential-sum approximation of power-law functions has been studied by Beylkin and Monzón (2005, 2010), while the root-exponential spectral behavior of power-law Hankel operators follows from Widom (1966). Theorem 1 combines these ingredients to obtain matching bounds in forecasting risk for a specified architecture class, but the extent of the new theoretical contribution beyond this combination could be more clearly distinguished.

Questions for authors
  1. Clarification of the contributions relative to prior theory.

Could the authors clarify which parts of the main complexity results go beyond the direct consequences of existing approximation and time-series theory? In particular, given the classical exponential-sum approximation results of Beylkin and Monzón and the Hankel spectral asymptotics of Widom, what are the essential new steps needed to establish Theorem 1 under forecasting risk? Similarly, what additional theoretical insight does Corollary 3 provide beyond the finite-prediction results obtainable from Hosking's exact partial autocorrelation formula?

  1. Relationship between the experimental models and the theoretical architecture classes.

Appendix G.1 states that the gated recurrence used in Figure 2 is affine in the previous state, rather than genuinely nonlinear in the state. Could the authors clarify how this implementation relates to the general nonlinear recurrence considered in Theorem 6? In addition, does the "gated GLA" label in Figure 2 refer to a specific reduced implementation of Gated Linear Attention, or to a more general input-gated recurrence? Clarifying this distinction would help establish which architectural conclusions are directly supported by the experiments.

4 comments

We thank the reviewer for the precise questions. We agree that the ingredients of Theorem 1 and the single-pole case of Corollary 3 are classical, and the revision says so in the paper.

What Theorem 1 adds to Beylkin and Monzón, and to Widom. For the exact power law the theorem combines positive exponential-sum approximation with the root-exponential Hankel spectrum. Lemma 15 now cites the exact input, Theorem 3.3 of Widom (1966) and the example after it, which gives eigenvalues exp⁡{−π2(α−1)n+o(n)}\exp\{-\pi\sqrt{2(\alpha-1)n}+o(\sqrt n)\} for the matrix ((j+k+1)−α)((j+k+1)^{-\alpha}). Putting the two inputs together in forecast risk takes four further steps, listed in the new App. B.11.

  1. The infimum is over state and context together. The Hankel rank of a truncated r-state kernel is not controlled by r, so the operator bound does not apply to it directly.
  2. The lower bound goes through the rank restricted to the context, a finite section of size Nr=eΘ(r)N_r=e^{\Theta(\sqrt r)} that still keeps sr+1s_{r+1} (Lemma 15), a two-branch argument on whether the context covers that section, and an antidiagonal multiplicity correction that costs a factor NrN_r. That cost is absorbed into the constant in the exponent, which is why the two constants differ while the exponent matches.
  3. Forecast risk weighs every lag, so the upper bound needs relative error at every lag and a context Lr=eΘ(r)L_r=e^{\Theta(\sqrt r)} that balances the tail. This gives the joint law for state and context in Table 1, which neither source states.
  4. The exponent carries over to analytic Laplace mixtures through a local Loewner argument, to the fractional geometry through Lemma 22 and Theorem 24, and to current-token affine gating (App. B.10).

Corollary 3 and Hosking. We agree that for one pole the law follows from Hosking's partial autocorrelations ϕkk=d/(k−d)\phi_{kk}=d/(k-d) and the Durbin and Levinson recursion, and Theorem 4.3 of Inoue (2002) proves it for fractional ARIMA(p,d,q) processes. We renamed it Proposition 3 and attributed it to Hosking (1981) and Inoue (2002). What the paper adds around it is threefold. Hard truncation costs Θ(L−1)\Theta(L^{-1}) while the coefficient tail is only Θ(L−1−2d)\Theta(L^{-1-2d}), so an analysis based on coefficient decay underestimates the context cost by a factor L2dL^{2d}. Several poles have no closed-form partial autocorrelations, and the law there follows from Fisher and Hartwig asymptotics together with the monotone density step of Lemma 18. A seasonal pole multiplies the cost by its period. The new Proposition R8 also uses Proposition 3, since a contraction margin acts as an effective context and Proposition 3 converts that context into a stability floor.

The gated recurrence of Figure 2. We agree that it is input-gated and affine in the state, a GLA-style diagonal gate with a fixed readout. The caption now says so and the legend is relabelled. It is a special case of the class of Theorem 6, and its input budget grows like δ−1\delta^{-1} as ρ→1\rho\to1, which Proposition R2 shows leaves the exponent of Corollary 7 unchanged. To test Theorem 6 on recurrences that are genuinely nonlinear in the state, we added a tanh RNN with ∣∣W∣∣≤ρ||W||\le\rho and a two-layer gated stack whose joint recurrence is nonlinear (Figure R1(c), App. G.15, Table R6). The tanh RNN stays above the envelope bound ∑j≥2(j−α−MKρj−1)+2\sum_{j\ge2}(j^{-\alpha}-MK\rho^{j-1})_+^2 at every margin, by a factor 1.18 to 3.08 at width 64, and its Monte Carlo first-chaos coefficients show no significant violation of the envelope (11) at any of 512 lags. The stack has a larger effective budget, so for it that curve is a reference only. It lies within sampling error of the curve at ρ=0.5\rho=0.5 and above it at smaller margins.

We would be grateful if you could let us know whether these points address your questions on novelty and on the gated model.

Dear Reviewer 5UsZ, thank you again for your review. The discussion closes on 18 November (AoE), and we would like to check whether our reply answers your two questions. On novelty, App. B.11 lists the four steps that Theorem 1 adds to Beylkin and Monzón and to Widom, Lemma 15 cites the exact result it uses, and Proposition 3 is now attributed to Hosking (1981) and Inoue (2002). On the gated model, the caption of Figure 2 now describes it as input-gated and affine in the state, Proposition R2 covers it, and App. G.15 tests recurrences that are nonlinear in the state. If anything is still unclear, we would be glad to answer it before the deadline. If the reply settles your questions, we would be grateful if you could take it into account in your assessment.

Reviewer_5UsZOpenReview ↗

Maintaining Rating of 2: Practical Scope, Novelty, and Readability Concerns

I thank the authors for adding the attributions to Hosking, Inoue, and Widom, Appendix B.11, and the tanh RNN experiments in Appendix G.15. However, after reading the revision, I maintain my rating of 2:

  1. Disconnect from practical sequence modeling: The core laws cover only scalar linear or first-chaos targets, while the nonlinear bounds require Gaussian inputs, uniform pointwise contraction, and artificial width-independent derivative caps in Appendix G.2. Per Appendix D.10 and Table R9, the state and stability laws exclude Attention, non-uniformly contractive selective models like Mamba and GLA, and higher-order nonlinear tasks outside the first chaos. All experiments remain synthetic 1D benchmarks where the gated cell's lower bound hits 00 for ρ≥0.99\rho \ge 0.99 in Table R5, and Proposition R1 mainly rationalizes existing S4D and LRU initializations.

  2. Limited theoretical novelty: Equation 19 equates regular-spectrum forecast risk to ℓ22\ell_2^2 error up to constants, making Theorem 1 largely an adaptation of Beylkin and Monzón's exponential sums and Widom's Hankel asymptotics to Ar\mathcal{A}_r. Appendices D.13 and H.2 also admit that Miller and Hardt's 2019 truncation argument already yields Corollary 7's rate, and Sections 4 and 6 similarly rely on classical fractional prediction and Fisher-Hartwig asymptotics, reading overall as a technical translation of classical results.

  3. Poor readability: The 10-page main text reads like a compressed theorem index, citing undefined appendix results and offloading key definitions, Table R9's scope caveats, and prior-work distinctions into 50 pages of dense appendices on pages 15 to 64.

Thank you for reading the revision and for the detailed assessment. Most of the limits you list are stated in the paper itself, in App. D.10, Table R9 and the Discussion, and we added several of them in the revision so that the scope is clear. Below we add a few facts that may help in weighing them.

Scope. We agree that the state and context laws concern a scalar linear target, and that the stability law needs Gaussian inputs and uniform contraction. Two points may still help to place these limits.

  1. The width-independent caps of App. G.2 belong to the experiments, where they keep a width sweep from mixing more modes with larger weights. Theorem 6 and Corollary 7 hold for any values of MM and KK, and Proposition R2 lets MKMK grow polynomially in 1/δ1/\delta.
  2. On Gaussian fractional data, attention is covered by the context law, which bounds every predictor that reads the last LL observations. Selective layers such as Mamba and GLA are covered when their gates stay away from one for every input, and they are outside the class otherwise. For targets that are nonlinear in the inputs the stability bound applies to their first-chaos part, as in our reply to Reviewer 94Ud and App. G.17.

Experiments and Proposition R1. The experiments are synthetic because the theorems compare a model with the optimum of its class and with the Bayes risk, and only synthetic data give both exactly. Table R5 shows the gated cell, whose budget grows like 1/δ1/\delta and reaches 796 at ρ=0.99\rho=0.99. At that budget the crossing lag of the bound lies beyond the context L=1024L=1024, so the bound is zero there. The diagonal SSM has a fixed budget, its bound is positive at every margin of Table R4 at L=4096L=4096, and trained SSMs come within a factor 1.67 of the class optimum for ρ≤0.99\rho\le0.99. Proposition R1 shows that Corollary 7 cannot be improved within the class beyond a logarithm, with a ladder of slow modes whose decay rates spread log-uniformly down to the margin. This agrees with the initialization of S4D and is close to that of LRU, and the theory adds how many modes and how small a slowest rate a given accuracy needs. Table R4 also shows what happens without the ladder. An initialization with decay rates near one stays 1.4 to 2.5 times above the optimum for 0.95≤ρ≤0.990.95\le\rho\le0.99, even after the readout is refit.

Novelty. We agree that the tools are classical, and the paper cites each where it enters. Equation (19) is the first step of Theorem 1, and App. B.11 lists the steps that follow it. The upper half of (19) fails under a spectral pole, which is the setting of Sec. 4. There the risk is the ℓ2\ell_2 error after fractional integration (Theorem 2), and a context of length LL costs Θ(L−1)\Theta(L^{-1}) while the coefficient tail is only Θ(L−1−2d)\Theta(L^{-1-2d}), so a reduction to coefficient error would miss the context cost by a factor L2dL^{2d}. On Corollary 7 we agree with you, and the revision says in Sec. 5.1, App. D.13 and App. H.2 that the truncation argument of Miller and Hardt gives its rate. Sec. 5 adds the bound on each lag, the sharpness of the rate (Proposition R1), growing budgets and stacks (Proposition R2), and the floor for forecasting fractional data from observations, whose exponent is 1 where the coefficient tail gives 1+2d1+2d (Proposition R8).

Readability. We agree that the main text is dense. For the camera-ready version, in addition to the changes listed in the general response, we will state in the main text the three appendix results it cites, Lemma 30, Proposition R8 and Theorem 33, add a short paragraph to Sec. 1 that summarizes the scope of Table R9, and give the steps of App. B.11 right after Theorem 1.

We respect your decision to keep the score, and we thank you again for the time spent on the paper and on the revision.

Reviewer_CNkbOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This work investigates predictive memory in terms of state dimension, context length, and stability in sequence models. The authors establish theoretical bounds on the number of modes required to approximate decaying memory. They also analyze fractional long memory processes, derive finite context bounds, and establish the relation between forecasting accuracy and the contraction margin of nonlinear recurrences.

Critical strengths
  • This work aims to address many relevant theoretical questions regarding predictive memory in terms of state complexity, context length and stability.
  • It makes several contributions, for example, for algebraically decaying memory, showing matching upper and lower bounds.
  • The paper provides extensive theoretical analysis.
Critical weaknesses
  • The paper tries to cover many distinct topics, which makes the contributions too spread out. While the Appendix provides additional details, the length of 49 pages raises questions about the balance between the breadth/depth of these contributions in my opinion. I found the paper's writing style difficult to read.
  • Even the title mentions long-memory capabilities, and LL is referred to as the recent observation length. In the experiments, it seems to be evaluated only up to 64, which can not be considered a real long-term horizon.
  • While the theoretical results seem to be interesting, the usefulness of the theories is difficult to judge in practice.
Questions for authors
  • Could the authors more clearly point out which existing sequence models (both RNNs and SSMs) have the exact assumptions used in the theories?
  • Could the authors provide broader experimental validations on both longer-horizon setups and non-synthetic datasets?
4 comments

We thank the reviewer for the review and reply to each point.

Length and writing. The appendix now opens with a roadmap that marks App. F, on multivariate memory, as a secondary extension that no main result depends on. The main text removes repeated comparisons and summarizes the new experiments in one paragraph. The revised PDF is longer than the submission, because the results and experiments asked for in the reviews are added in blue at the end of their sections. In a further revision we plan to move App. F to the supplementary material, which shortens the appendix by about ten pages. We kept it in place for now so that the appendix letters cited in the reviews stay valid. For the camera-ready version we will also move the experimental setup into Sec. 7.

Long horizons. We agree that L=64L=64 is short, and it is in fact too short to test the stability law. At L=64L=64 the class optimum is already 4×10−64\times10^{-6} at ρ=0.95\rho=0.95, so there is no floor left to measure. The revision adds trained sweeps at L=1024L=1024 and L=4096L=4096 (Figure R1(b), Figure R5, Table R4), forecasting from a FARIMA path of length 2202^{20} with windows of 4096 observations (Table R7), and the exact class optimum at margins down to δ=0.002\delta=0.002 with untruncated targets (Table R1). Figure 1(b) of the submission already evaluates the context law up to L=105L=10^5.

Non-synthetic data. The theorems compare a model with the best model of its class and with the Bayes risk of the target. On real data neither is known, so a real-data benchmark could show a gap without telling us which part of it the theory explains. Forecasting FARIMA from its own noisy observations is the closest setting in which both quantities can be computed exactly, and we added it. We do not add a real-data benchmark in this revision.

Q1, which models satisfy the assumptions. Table R9 in App. H.1 answers this architecture by architecture. LTI state-space layers (S4, S4D, S5, LRU) satisfy the assumptions of Theorem 1 and of Corollary 7 when their transition has operator norm below one. Selective layers such as Mamba, GLA and Gated DeltaNet satisfy the assumptions of Corollary 7 when their gates stay away from one for every input and their injection is bounded, and Proposition R2 extends this to fixed-depth stacks. Contractive Elman, LSTM and GRU cells are covered by Corollary 7, and on Gaussian fractional data any model that reads only the last LL observations is covered by the context law of Proposition 3.

Usefulness in practice. Three consequences can be acted on.

  1. Initialize decay rates log-uniformly from the target margin up to order one. Most rates stay close to where they start. In our runs a log-uniform initialization ends with eigenvalues close to optimal, while an initialization near one stays 1.4 to 2.5 times above the optimum for 0.95≤ρ≤0.990.95\le\rho\le0.99 even after the readout is refit (Table R4). Corollary 7 also says how small the slowest rate must be for a target accuracy.
  2. For long-memory data with fractional strength dd, a context of length LL costs V∞d2/LV_\infty d^2/L in forecast variance, so halving that excess needs twice the context, and estimates based on coefficient decay understate the cost by a factor L2dL^{2d}.
  3. When adding width no longer lowers the error, look at the contraction cap. In the width sweep at ρ=0.8\rho=0.8 the error reaches the class optimum for that contraction from eight modes on and stays there, and only a contraction closer to one lowers it further (Figure R5(c)).

Soundness. We would like to understand the concern behind the soundness score. If you can point to a statement or a step, we will address it directly in the discussion.

Dear Reviewer CNkb, thank you again for your review. The discussion closes on 18 November (AoE), and we would like to know whether our reply addresses your concerns. The revision adds trained sweeps at L=1024L=1024 and L=4096L=4096 and forecasting from FARIMA paths with windows of 4096 observations, Table R9 lists for each architecture which result applies and under which condition, and our reply gives three practical consequences and explains why we did not add a real-data benchmark. About the soundness score, we would be grateful if you could point to the statement or step that concerns you, so that we can respond before the deadline. If the changes resolve your concerns, we would appreciate it if your assessment could reflect them.

Thank you for the revisions, especially addressing parts of my concerns in Q1 and its usefulness in practice. By soundness, I meant the paper is very dense which makes it hard to follow, which is also pointed out by other reviewers. Having no real-data benchmarks and the style of the paper are points that lead me to keep my score.

Thank you for the reply and for explaining the soundness score. We are glad that the revision answers part of Q1 and the question on practical use.

We agree that the paper is dense. For the camera-ready version we will move the experimental setup into Sec. 7 and App. F to the supplementary material, state in the main text each appendix result it cites, and summarize the scope of Table R9 in Sec. 1. On real data our reason is unchanged. The theorems compare a model with the optimum of its class and with the Bayes risk. Neither is known on real data, and forecasting FARIMA from its own observations, which the revision adds, is the closest setting where both can be computed.

Since the concern behind the soundness score is the density of the paper, which the presentation score also reflects, we would be grateful if you could look at the soundness score again with this in mind. We respect your decision on the overall score, and we thank you again for the review.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank the three reviewers for their careful reading and for the concrete suggestions. We have uploaded a revised PDF and a revised supplementary material, which adds the notebook of the new experiments with the cache of all its runs and a script that checks the constant of Lemma 15. All changes are set in blue, and new results, figures and tables are numbered R1, R2 and so on, so every number in the reviews still points to the same statement.

Our contributions. The paper asks how much state, context and contraction margin a sequence model needs in order to forecast a target with algebraic or fractional predictive memory, with error measured in forecast risk. For algebraic memory the best error with r modes is e−Θ(r)e^{-\Theta(\sqrt r)}, so accuracy τ\tau needs r=Θ(log⁡2(1/τ))r=\Theta(\log^2(1/\tau)) modes (Theorem 1). For fractional memory the predictive geometry changes, and the context cost is V∞d2/LV_\infty d^2/L at leading order (Proposition 3). For uniformly contractive recurrences the first-chaos memory has an exponential envelope, and accuracy τ\tau forces the contraction margin below τ1/(2α−1)\tau^{1/(2\alpha-1)} up to a logarithm (Theorem 6 and Corollary 7). The revision shows that this last bound is attained up to a logarithm by a model that also attains the state law, so the three laws fit together.

New results.

  • Proposition R1. Corollary 7 is attained up to a logarithm by a diagonal model with O(log⁡2(1/δ))O(\log^2(1/\delta)) modes, so the stability law is sharp within the class (Sec. 5.3, App. D.12).
  • Proposition R2. The derivative budgets enter Corollary 7 only through a logarithm. The corollary therefore keeps its exponent when the budgets grow polynomially as the margin closes, which covers the gated cell of Figure 2 and fixed-depth stacks of contractive layers (App. D.11).
  • Remark R3 with Propositions R7 and R8. The envelope of Theorem 6 carries over to models that read a Gaussian observed process. For FARIMA(0,d,0) the margin acts as an effective context, and the risk is at least σ2d2δ/{16log⁡(e/δ)}\sigma^2 d^2\delta/\{16\log(e/\delta)\} for small δ\delta, with an explicit bound at every margin (App. D.13).

New experiments (Figure R1 in Sec. 7, protocol and tables in App. G.11 to G.17).

  • The exact class optimum, computed as a convex program, lies between the explicit bound of Lemma 30 and the construction of Proposition R1.
  • Trained diagonal SSMs at context L=4096L=4096, where the stability law can actually be tested for ρ≤0.99\rho\le0.99, reach 1.00 to 1.67 times the class optimum. Refitting only their readout brings them within 3% of it.
  • A tanh RNN with ∥W∥op≤ρ\|W\|_{op}\le\rho, which is nonlinear in the state, stays above the envelope bound, and its Monte Carlo first-chaos coefficients show no significant violation of the envelope (11) at any lag. A two-layer gated stack, covered by Proposition R2 with a larger budget, lies within sampling error of that curve at ρ=0.5\rho=0.5 and above it at smaller margins.
  • Forecasting FARIMA(0,d,0) from its own observations, where the exact class optimum stays within a factor 1.9 of the bound of Proposition R8, and a target that is nonlinear in the input.

Positioning and presentation.

  • App. B.11 lists what Theorem 1 adds to the exponential sums of Beylkin and Monzón and to the Hankel spectrum of Widom, and Lemma 15 now cites the exact result used, Theorem 3.3 of Widom (1966) and the example after it.
  • Corollary 3 is renamed Proposition 3 and attributed to Hosking (1981) and Inoue (2002).
  • Sec. 5.1 states plainly that the truncation mechanism behind Corollary 7 is classical (Miller and Hardt, 2019).
  • Sec. 1.1 and App. H.2 add the literature on memory capacity, information processing capacity and the edge of chaos.
  • Table R9 in App. H.1 states which architectures each result covers and under which condition.
  • A roadmap opens the appendix and marks App. F as a secondary extension that no main result depends on. Repeated comparisons with curse-of-memory results were removed from the main text.
  • The abstract no longer says that the experiments reproduce the state law. The state and context laws are checked by exact computation, and trained models are tested against the stability floor.

For the camera-ready version we will narrow the title to "The Cost of Long Memory: Sharp State, Context, and Stability Laws for Algebraic Predictive Memory", move the experimental setup of App. G.1 to G.4 into Sec. 7 so that the setup comes before the results, and shorten the main text further. In a further revision we also plan to move App. F, on multivariate memory, to the supplementary material, which shortens the appendix by about ten pages. We kept it in place for now so that the appendix letters cited in the reviews stay valid.

If any step of a proof looks doubtful to a reviewer, we would be grateful to hear which one, and we will address it directly in the discussion.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.