- 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
-
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?
-
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.
-
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
Part II
W4, experiments. We agree that the sweep could not test Corollary 7, and the revision explains why. At the class optimum is already at and below for , so no stability floor is left to measure. The new experiments address each of your points.
- Context. Trained sweeps at and . At the crossing lag satisfies for every , so these points probe the asymptotic regime.
- Derivative bounds that change with . Proposition R2 shows that budgets growing like leave the exponent of Corollary 7 unchanged. The gated cell has , 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 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 it levels off between and , 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 , with the slowest rate of order up to a logarithm and about 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 , 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 (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 (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 (Proposition R8). This floor has exponent 1, where the coefficient tail alone gives only . 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 . Then numerical evidence: the exact class optimum for FARIMA has local slope 1.08 to 1.14 in for and , close to 1 and far from 1.5 and 1.8 (Table R3). Trained SSMs that forecast one exact FARIMA path of length stay above this optimum, at 1.11 to 4.52 times it for , and their readout refit is within 7% (Table R7). For the nonlinear target 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.
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 , 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 , 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, 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 , with budgets that grow at most polynomially in , the risk on an algebraic target is at least of order 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.
Part I
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 ρ 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.
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≤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 L2 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.