Provable Length Generalization in Sequence Prediction via Spectral Filtering
Authors: Annie Marsden
Evan Dogariu
Naman Agarwal
Xinyi Chen
Daniel Suo
Elad Hazan
Venue: ICML 2025 poster (2025)
Keywords: sequence prediction; length generalization
Primary area: general_machine_learning->sequential_network_and_time_series_modeling
TL;DR: We define a measure of length generalization and provide provable guarantees based on this notion for the spectral filtering algorithm.

Abstract: We consider the problem of length generalization in sequence prediction. We define a new metric of performance in this setting – the Asymmetric-Regret– which measures regret against a benchmark predictor with longer context length than available to the learner. We continue by studying this concept through the lens of the spectral filter-ing algorithm. We present a gradient-based learn-ing algorithm that provably achieves length generalization for linear dynamical systems. We conclude with proof-of-concept experiments which are consistent with our theory.

Provable Length Generalization in Sequence Prediction via Spectral Filtering
Annie Marsden" Evan Dogariu"
Naman Agarwal
Xinyi Chen Daniel Suo
Elad Hazan 12
Abstract
dictor with longer context. Unlike standard regret, which assumes both the learner and benchmark operate under the same conditions, Asymmetric- -eggret explicitly accounts for the context length discrepancy, offering more realistic evaluation of length generalization in resource-constrained settings.
We consider the problem of length generalization in sequence prediction. We define new metric of performance in this setting - the Asymmetric- Regret- which measures regret against a bench- mark predictor with longer context length than available to the learner. We continue by studying this concept through the lens of the spectral filter- ing algorithm. We present gradient-base learn- ing algorithm that provably achieves length gen- eralization for linear dynamical systems. We con- clude with proof-of-coneept experiments which are consistent with our theory.
We study length generalization through the lens of spectral filtering algorithms, class of methods known for their ef- fectiveness in learning linear dynamical systems (LDS) with long memory (Hazan et al., 201 Spectral filtering meth- ods have recently been used to develop state space models that achieve state-of-the-an (SOTA) performance in LLMs, improving both efficiency and scalability (Gu et al., 202 bb; Poli et al., 2023; Gu & Dao. 2023). In this work. we prove that spectral filtering algorithms can generalize across con- text lengths while maintaining strong theoretical guarantees regret. This is the first result, to the authors' knowledge, providing such provable guarantees in the setting of learning linear dynamical systems.
1. Introduction
Sequence prediction is fundamental problem in machine learning, with applications that span natural language pro- cessing (NLP), forecasting, and control systems. A com- mon challenge in these tasks to determine how much past information, known as context length, should be used to make accurate predictions. Although longer contexts often improve performance, they come with increased computa- tional and memory costs, making it impractical to store and process entire sequences, especially during training.
1.1. Our Contributions
Consider online sequence prediction in which the predictor iteratively receives input ut E R. and then makes a pre- diction ie E Rd.. of the output, after which the true output y/ revealed. The goal of the predictor is to minimize error according to given convex and Lipschitz loss function (14, Dt). In this work consider the class of spectral filtering predictors, introduced by Hazan et al. (2017b). A spectral filtering predictor is characterized by parameters (T, M k) and outputs predictions ÿe of the form
This challenge raises a key question: Can we design learn- ing algorithms that effectively operate with limited context during training while still generalizing to longer sequences test time? This property, which we call length generaliza- tion, is particularly relevant in large-scale models, such as large language models (LLMs), which struggle to extrapo- late beyond the context lengths seen during training. Despite extensive empirical research on this issue, formal theoretical guarantees on length generalization remain elusive.
Ue = 9i-1 +
Maaa-12000
where u(t-1):0 E XT is a matrix whose columns are the previous inputs u1-1, 2............................... (possibly zero-padded as necessary), {Øt ( are the 7-dimensional spectral fil- ters, {M.) C Rdua dda are matrices which are learned online, and k is the number of filters used. Hazan al. (2017b) provide algorithm to learn {M,} and show this achieves nearly optimal regret bounds when measured against the best Linear Dynamical System (L.SS) predictor. We explore whether the full history u(r-1): is needed to learn {M. More broadly, we explore whether predic-
To address this, we introduce a novel performance metric, Asymmetric-Regree which quantifies the regret of a predic- tor with a limited context length compared to an ideal pre-
Equal contribution 'Google Deep.Mnnd "Princeton Uni- versity. Correspondence to: Annie Marsden <anniemars- den@ connggooll..omm. Evan Dogariu <dogariu@ @ weroilieooooooooo......
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
tor classes and corresponding online learning algorithms exist that can achieve context length generalization- that is, they use only short recent history during learning but perform nearly as well as if they had used the full, much longer history length. Of course, predictors which perform poorly on systems that require long memory can trivially achieve context length generalization if their performance poor regardless of the context length used. Notably, spec- tral filtering predictors excel in systems with long memory (Hazan et al., 2017b).
which aim use low memory typically fail. Critically, Theo- rem 1 holds even for these marginally-stable systems. When interpreting this result, it's important to note that the class of spectral filtering predictors IIş which use the full context length are provably able to predict well on marginally-stable Linear Dynamical Systems (Hazan et al., 2017b)'. There- fore, this result implies that spectral filtering predictors are able to context length generalize in nontrivial way.
Inspired by the way in which Theorem is sensitive the spectrum of A, we develop novel variation on the Spec- tral Filtering algorithm, presented in Algorithm 2, which achieves robust length generalization without added assump- tions on the spectrum of A (whenever the context-length is at least T1/1). Algorithm achieves this by using two autoregressive components yt-1 and 3/-2 to construct its prediction ÿt of yt. We provide our main theorem of this work.
To properly understand context length generalization, we introduce the notion of Asymmetric-Regret. The idea is to consider the regret of learning a predictor from a class which is only allowed to use context length T'' against the best predictor which is allowed to use (potentially much longer and therefore asymmetric) context length L. Let I denote the class of predictors in IT which use context length L. Given an algorithm A(I') which learns over predictors from some class II,, the Asymmetric-Regree over horizon T is
Theorem 2. Let T E Z 2 and q E [1 (og(lo((T)/)) log(T) ]]]
Consider a sequence (y1,...,9TT) ,r)) generated by un- known and noiseless linear dynamical system defined by matrices (A, B, C, D) as per Eq. 1. Assume the imput se- quence (n:(t-1) is sufficiently well well-conditioned. satisfying ETD (T - 1yuuu x =(2 (2()) I. Let A(b) denote Algo- rithm 2 operating with context length L, and let 11 denote the class of spectral filtering predictors using context length L. For the squared loss li(y. y²) = ly u--y y/ and sufficiently
RegretAsym,7 Asym,T (A(I',IIz) def T
E (ve, De )
min (Vv,, rlll
Our first result shows that spectral filtering generalizes from a history of 744 where q E [0, 1]. to T for certain linear dynamical systems. It is formally given in the following theorem.
large T, it holds that:
Regret Asym,
Regre T (A(T9), .IŞF) < Õ(VT).
Theorem 1. Let T E Zzo and q E [0,1]. Con- sider a sequence (M1,..., generated by an unknown and noiseless linear dynamical system defined by matri- ces (A, B, B,,, D) as per Eq. 1. Assume the input se- quence Uo:(t-1) is sufficiently well-conditioned, satisfy-
Finally, we experimentally confirm the results of Theorem and Theorem on synthetic data generated by an LDS. Interestingly, we find that Theorem 1 accurately predicts when length generalization is possible; indeed, when the data is generated by LDS which has eigenvalues in the "bad" range [1 - (og(()/((TT)))))) the limited context length spectral filtering predictors are unable to length generalize. However, when the data is generated by an LDS which has eigenvalues "hugging" this bad range (i.e. either just smaller than 1 - Log(T)/(8T)) or just larger than 1 - 1/(2T5/4), the limited context length spectral filtering predictors successfully length generalize, demonstrating the sharpness of our analysis. Next, we see that adding the second autoregressive term allows for robust length generalization on marginally-stable systems with no
ing ETD - t)u,uu > (21C)
I. Suppose the log(T) U
VT
-1/(27//1) we find that
eigenvalues of A lie within the range [0, 874
[1- [1-27674
= 1].
Let A(L) denote Algorithm 1 operating with context length T,, and let THE denote the class of spectral filtering pre- dictors using context length L. For the squared loss Eely. s/) -y--y' and sufficiently large T, it holds that: Regret A (A(T"), ITF) S O(VT).
This theorem indicates that for any q E 10, the Asymmetric-Regree is bounded by Ö(VT). However, as q decreases, the class of linear dynamical systems for which this bound holds becomes more restricted due to the eigen- value conditions on A. The spectrum of A determines the memory of the system; when the eigenvalues of A are 1, the system is only marginally-stal and standard predictors
'The only LDS's s for which there can be any useful results are those with A's eigenvalues in [-1, 1), i.e. marginally-stable sys- tems. We recall that the spectral filtering principle can be readily applied to handle negative cigenvalues in [-1, 0] (see Appendix of (Agarwal et al., 2023), for example). For ease of presentation. we focus on capturing the length generalization effects of eigen- values in [0, 1] in the sequel, and so we suppose without loss of generality that 2
2

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
spectral assumption. Lastly, we conduct experiments using the STU neural architecture to test the hypothesis that this architecture should simply length generalize without any task-specific engineering. We consider the induction heads synthetic task and find that the out-of-the-box STU neural architecture does indeed enjoy some level of length general- ization. This suggests that incorporating spectral filtering into neural architectures, like the STU, may provide im- proved length generalization in deep learning applications. We leave further empirical study on this for future work.
provable guarantees and can have varying empirical perfor- mance (Kazemnejad al., 2024). There have also been extensive investigations into the ability of neural networks to length generalize and the role that various features play in this, for example see (Anil et al., 2022; Murray & Chiang, 2018; Ychudai et al., 2021; Zhang et al., 2022; Newman et al., 2020).
In contrast, our investigation starts from the theory of regret minimization in games and online learning. Regret mini- mization has the advantage that it implies generalization in the statistical learning setting, see e.g. (Cesa-Bianchl et al., 2004) and is usually accompanied by efficient algorithms such as online gradient descent, see e.g. (Hazan et al., 2016). Our new notion of Asymmetric-Regee metrie information access between the online learner and the benchmark class.
1.2. Related Work
The literature for sequence prediction is too broad to survey in detail, so we give few highlights of the recent rapid ad- vancements. The most notable progress includes the Trans- former model (Vaswani et al., 2017) that incorporates an attention mechanism for accurate sequence prediction in many domains (Brown et al., 2020; Dosovitskiy et al., 2020; Jumper al., 2021). Transformer models and their attention layers have memory/compuration requirements that scale quadratically with context length. Many approximations have been proposed (see (Tay et al., 2022) for recent sur- vey).
incorporates asym-
2. Background and Setting
In the online sequence prediction setting the predictor iteratively receives input u, and makes prediction de of the output, after which the true output ye revealed. The goal is to minimize error according to a given (convex Lipschitz) loss function le Dt).
Motivated by the high memory and compute requirements of transformers, state space models were revisited starting from (Gu al., 2020; 202 who propose and develop the HiPPO theory. Gu et al. (2021a) develop the S4 parame- terization to address the bottlenecks of training efficiency, performance and numerical stability. Further works in the area show SOTA performance and include (Gupta et al., 2022; Smith et al., 2023; Orvieto et al., 2023; Gu & Dao,
In online learning, we usually do not make statistical as- sumptions about the generation of the input sequence. As such, performance is measured relative to a certain bench- mark class of predictors. A prediction algorithm A is mea- sured by regret, or difference in total loss, vs. class of reference predictors Me (such linear predictors), i.e.
2023). State space models are very efficient for training and inference, but can suffer in long-contex: applications. This motivated the use of spectral filtering technique for learning marginally-stadee stablee linear dynamical systems (Hazan et al., 2017b; 2018). This technique was incorporated to a neu- ral architecture in (Agarwal et al., 2023), that was recently shown to perform well across several modalities (Liu et al., 2024).
Regret, (4, II) = Σ C(
min TEn
Le DC).
This formulation is valid for online sequence prediction of any signal. We are particularly interested in signals that are generated by dynamical systems. A time-invariant linear dynamical system is given by the dynamics equations
Ft+1 = Ax + Bu + we ye+1 Crz + Duc + St (1)
From an applied perspective, generalization in sequence prediction has been studied in (Hou et al., 2024) through the theoretical lens of Turing programs. They propose a methodology that empirically improves length gener- alization across a diverse set of tasks. There are also many architecture-specffi approaches to improving length generalization, usually in the context of language mod- els, such as ALiBi positional embeddings for transformers (Press et al., 2022), recursive application of deep networks (Schwarzschild et al., 2021; Bansal et al., 2022), self- attentive recurrent sequence model called the "Universal Transformer" (Dehghani et al., 2018), and the Neural GPU (Kaiser & Sutskever, 2015). However, such methods lack
where x, is the (hidden) state, u, is the input or control to the system, and ye is the observation. The terms wey Se are noise terms, and the matrices A, B, C, D are called the system matrices.
Many methods exist for linear dynamical systems and their performance guarantees rely heavily on the spectrum of A. The system is unstable whenever |Amax (A)l norm of the observations tends towards infinity, stable when | < 1 and marginally-stable if |mmax (A) = 1. In the stable setting, if |>max (A)l = -1-5 < 1, typical methods (i.c., Kalman filtering) must use a history of at least > } previous states to accurately capture the dynamics. As 8 gets
because the
3

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
smaller (i.e. long memory), it therefore becomes difficult for methods directly learn these relationships. Methods that learn system matrices require knowledge of the dimension of the hidden state (which may be very large) and can also be unstable for systems with long memory. Through a particular parameterization and convex relaxation, however, the spectral filtering algorithm is able to efficiently predict observations from marginally-stabi systems with sublinear regret. We provide more background on spectral filtering in Section 2.2, and more details on the rich theory of linear dynamical systems may be found in (Hazan et al., 2020).
bound on the Asymmetric Regret would immediately apply to this alternative notion of regret since the algorithm is only given more power, That said, this alternative notion of regret could provide a different landscape of results. For instance, there may be signals (like a linear dynamical system with asymmetric transition matrix) that can still be learned with short context length but require the full history to be predicted accurately.
2.2. Spectral Filtering
Spectral filtering is a notable deviation from the standard theory of linear dynamical systems that allows efficient learning in the presence of arbitrarily long memory (Hazan et al., 2017b). The idea is to project the sequence of inputs to small subspace that is constructed using the special structure of discrete linear dynamical systems. The output of the spectral filtering predictor is represented as
2.1. Context Length Generalization and the Syymmetric-Rerree metric
We say that an online predictor has context length L if it bases its prediction de only on information from the previous L timesteps, i.e. U and ---t-L- The key question in our work is whether there are algorithms which learn and predict using a short context length, but perform as well as had they been allowed to use long context length. To formalize this notion, we introduce Asymmetric-Regue whose definition we restate here:
Út yt-1 Σ Mala-1)o00
where u(e-1):0 E IR XT is a matrix whose columns are the previous inputs u,.1,..., Ug (possibly zero-padded as nec- essary), { are the 7-dimensional spectral filters that can be computed offline given the target sequence length T, and {M C Rdux Xd. are the matrices parameterizing the model. These spectral filters are the eigenvectors of the matrix constructed as the average of outer products of the discrete impulse-response functions as we now detail.
Definition 3 (Asymmetric-Rege Regret), Let I1 be class of predictors which use context length L' and let TI be a reference class of predictors which use context length L. The Rsymmelric-Regreet with respect to (convex Lipschitz) loss le over horizon T of an algorithm A(L') which tries to learn a predictor from Nham is
T
Regret A (A(L'), 11.
del
(ye Dr (
Let Ma.r = (1 a)),, ...., a"] be the (weighted) impulse-responss response vector corresponding to one dimensional linear dynamical system with parameter a unfolded to T time steps, and consider the symmetric matrix
T
min rell
Leve. 0P).
HT del S [oo.TWo
(3)
To gain a better understanding of Asymmetric-Regre note that the typical notion of regret in sequence prediction sets L' ='= T for the given class of predictors and sets L = T for the given reference class of predictors If by default. In this case Asymmetric-Regree recovers typical regret.
Since HT a real PSD matrix, it admits a real spectral de- composition, and the (uon-negative) eigenvalues can be or- dered naturally by their value. Let { E IR, oj E R 1 be the eggevvalu-eiieenvecto pairs of Hr ordered to satisfy 2 02 > 2 ad- The spectral filters .i,..,, di are exactly those first k eigenvectors corresponding to the largest eigenvalues. The spectral filtering class is further parameterized by matrices M,,.., Mr E RRdm The output at time t then given by equation (2).
Regret (A, I1 Regret Asym.r (A(T), I1)
However, if T'' < T. any upper bound Regret (A(L'), 1175) immediately implies upper bound on Regret (A, IIeef) since the algorithm A(T) can choose to only use context length L' and ignore the rest. Therefore, Asymmetric-Rege Regret is a stronger notion than typically used. Another possible notion of regret that aligns more with the literature of length generalization for language models is to restrict the algorithm A(L) to update itself using context length L' but to allow to use full context length when making predictions. Note that any
The following theorem establishes that the spectral filtering class of predictors approximately contains bounded linear dynamical systems with positive semi-definite A. The exact constants are left out for simplicity of presentation, but appear in the original work.
Theorem 4 (Simplified from (Hazan et al., 2017a)). Given any linear dynamical system parametrized by A, B,C, D
4

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
such that A is a PSD matrix with ||||| 1, there exists matrices Mi;-.. MR. such that for all T and all sequences UI:T, ut:T,I|uell S 1, the following holds. Let V be the sequence generated by execution of the LDS via (1) and SE be the sequence generated by Spectral Filtering via (2).
statement on length generalization, we present the following performance guarantee. Note that we prove the following for (A, B, C, I)LLDS rather than (A, B, C, D) which is without loss of generality since we can consider the imput as Dun...., Dur.
Virr
Then for all t E [T],
Theorem 5. Lel T E Zzo and E [0, Con- sider a sequence (y1....,, generated by an unknown and noiseless linear dynamical system defined by ma- trices (A, I) as per Eq. 1. Assume the input se- quence (Mo((t-1) is sufficiently well-conditioned, satisfy-
11 LDS
Vt SF|| ~ ToR(L),
Theorem 4 establishes that Spectral Filtering can predict long memory sequences since the statements holds even over marginally stable linear dynamical systems.
ing Σt (T -t)ucu = (2Q1)B)
) L. Suppose the eigenvalues of A lie within the range [0, log
vT
STT
3. Learning with a Short Length Generalization for Linear Dynamical Systems
[1- 275/7
a (log(T) log (Tda)) 2 [B][IC|| and assume T 2 (4k (Tkloo())/ICCllIBBB
37777.1). 1). Let
Algorithm I satisfies:
Regret Asym,T (A(T9), IT
In Algorithm 1, we modify the classical online learning algorithm for spectral filtering to use a shorter context win- dow. To properly define our notion of length generalization, we need to distinguish between context lengths. Thus we introduce the notation for the loss observed with a context length L: letting (M, L) denotes the prediction of ye using M = [M1.... ................................ M&] and context window size L as in Eq. 4 of Algorithm I we have
S so <01111 log( log(T)/T).
The proof of Theorem 5 is in Appendix B with a high-level overview at the end of this section. This theorem shows that the sequence M ......"'' MM constructed by Algorithm 1, even when using a reduced context length of size T9, able achieve regret ((VT) when compared to the best spectral filter that uses full context length T. To gain better understanding of the needed assumption on the spec- trum of A, first suppose that all the eigenvalues of A are bounded by 1 - 5. Then the extent to which the input ut-to affects the value of y is roughly (1 - 5))a, since the hid- den state is multiplied by A to many times. This becomes negligible when to much larger than 1/5 and implies that W may be forgotten. This intuition explains why length generalization is possible for the first region of eigenvalues 00, 1 - log log-oo) (T) Indeed, letting 5 = log(T)/88 /8T" and to = T (which is much bigger than 87 /og((T for large enough 7) we see that when the spectrum of A is smaller than 1- ò, after to many steps we can forget about the pre- vious inputs ut-to- The second part of the range- i.e. that the spectrum of A can lie between [1 1/(275/1), 1]- is a special feature of spectral filtering's ss ability efficiently cap- ture long memory effects and is rather technical. The "bad region" is exactly the range where the eigenvalues aren't 't small enough that u4-to can be forgotten for to 2 T but also aren't 't large enough that spectral filtering is naturally able to capture them. Numerically, the range is very small for large T' and reasonable q.
4 L) ()(M, -vell 12
Note that this is overloaded notation compared with (v) v/) which measures the loss of the true y with the predicted y/ as used in our definition of regret. To provide a precise
Algorithm 1 Spectral Filtering with Limited Context
I: Input: k > 0, > 0, L > 0, > 0. Initialize M. E Rdmi for i [k] and set M [M]..... Mt).
Let Φ1:k be the largest eigenvectors of Hy defined in Eq. 3 with corresponding eigenvalues 1..k and let (T)(-) denote the projection to convex set K.
2: for (= = 1, 2, ...,,? T do
3: Compute and predict
Ú. = Ut-1 +
Σ
M
() (1). (4)
4: Observe yt. denote (e(M*,) 1igte- - yell 2 and update and project onto the low Frobenius norm ball
M++1 + M T/ (Mr
Motivated by the limitations of Theorem 5, in order pro- vide a length generalization that is robust to the spectrum of A, we introduce a variation on the classical Spectral Fil- tering algorithm. presented as Algorithm 2. This algorithm where K,, {M E Bexdd Xdu; ||M S r, ri e [k]] uses the two most previous outputs yt-1 and yt-2 when 5: end for
M++1 =TK TT (NT
making a prediction ÿr of yt-
5

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
This algorithm has a slightly different construction of spec- tral filters. Indeed, they are the eigenvectors of the following matrix
High-Level Proof Overview. The general proof technique for both Theorem 5 and Theorem 6 is the same. First, us- ing standard online gradient descent results from (Hazan et al., 2017b) we prove that the iterates M' achieve O(v regret as measured by the context-length restricted loss Ei ((M, L). That is,
Nr def !/" "aariia
(5)
where Ho,T = (1 (,, a²), just by using one extra autoregressive term, our adapted algorithm is able to enjoy robust length generalization in the sense that whenever the context window is at least /1/ then no extra assumptions on the spectrum of are neces- sary to achieve our notion of length generalization. We state this formally in the following theorem.
Interestingly,
T Σ EG(M'.D L) S min MEK.
T Σ (((M,)) (6)
Next we prove that there is a unique Mr which minimizes the loss on the full T-length context and this M, achieves length generalization in the sense that it achieves small loss even when only allowed to use context length L. That is
Algorithm 2 Spectral Filtering with Limited Context and Two Autogressive Components
Σ E4(M7 L) S Σ T) O(VT).
(7)
1: Input: k > 0, T > 0, L 0, 0. Initialize M, E Rdmiddn for i E [k] and set M = [M]..., M,]-
t=1
We combine Eq. 6 and Eq. 7 to get the final notion of length generalization that
Let Φ be the largest eigenvectors of Nr-2 defined in Eq. with corresponding eigenvalues 0i:k, and let Tx(() denote the projection to convex set K.
T
Σ L L) S min MEX.
Σ
((M,L)+
2: for = 1, ...,? I" do
3: Compute and predict
d1- = 21--1 - V--2 + Mfuu-1 + M/ui2
Σ M (o.-//1))
T)
4: Observe y/t, denote 4cM* 11 - Ve 12 and update and project onto the low Frobenius norm ball
The difficult result to prove is Eq. 7. The high level idea is that when Vi:t evolves as a noiseless LDS and when the input 10:(t-1) is sufficiently well-conditioned, then Et (M,, T) is strongly convex and the minimizer ap- proximately recovers collection of "true" matrices which are generated by the underlying linear dynamical system. The second key idea is that if an algorithm had access to these "true" matrices then would be able to achieve small loss even when restricted to a small context-length L. < T. The extent to which these recovered matrices can achieve small loss when restricted to the small context-length de- pends on the way the algorithm chooses to predict yr- In the case of Algorithm I where ye is predicted based only using only one autoregressive term, even having access to the true matrices is not enough to accurately predict yt. However, in the case of Algorithm 2, having access to the true matrices as well as a second autoregressive term allows accurate pre- diction of y even when restricted to small context-length window.
M M ne (Mr
M+ = TTK (NT44),
where K,, {[M,. M&] s.t. ||Mill S r, Vi E [R]).
5: end for
Theorem 6. Let T E E o and E
E [ (og(lo((T)/8) log(T)
Consider sequence (y1....,3r" generated by an un- known and noiseless linear dynamical system defined by matrices (A, B, I) as per Eq. 1. Assume the input sequence (o-(t-1) is sufficiently well-conditioned, satis- fying ET= (T - t)ucu Z (2C1BB) I. Let k Ω (log(T) logg (Tda)), r 2 |BI|ICT and assume T 2 (4klog (T)/ Algorithm satisfies:
Regret (A(T"),
4. Experiments
< s (1B1111111 log(T)>
4.1. Linear Dynamical System
The proof of Theorem is in Appendix C and we now give a high-level overview.
We can empirically verify Theorem and Theorem 6 in an online sequence prediction task where the data is gen-
6

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
erated by noiseless LDS. We refer to "bad" region of
Online LDS Losses (Region A)
eigenvalues (1 (Tg(()) ( (877//) 1 1/(275/4) Re- gion B, and we define Region A to hug Region B on both sides as shown in Figure 1.
6.6
7
8 0.34
Region A
4.34
Region
6:30
3803
4000
4000
13000
18000
Figure 1. Region is the interval of cigenvalues for which Theorem 5 does not provide length generalization. Re- gion A hugs both sides of Region B (Region A is 0.9- (1-log (1-log(T)((ST7/*))
Figure 2. Loss for Algorithm with eigenval-
Region A.
Region B). This ensures that Region A will contain bad eigenvalues as decreases from 7/8 and eigenvalues in Region B are bad for q < 7/8.
Online LDS Losses (Ragion B)
774
6.3
0
4.34
Theorem 5 predicts that if all the eigenvalues lie outside Region B, then spectral filtering will length generalize from T7/8 to T. To confirm this, we generate a random LDS (hidden dimension: 512) with half of its eigenvalues sam- pled from each part of Region A. The online prediction losses are plotted in Figure 2 for different choices of context length 7 where T' 214 and k 24. As expected from the theory, context lengths approaching T closely match the performance of the optimal spectral filtering predictor with full context.
0.33
2003
4000
$0.00
10000
120M
1000
Figure 3. Loss for Algorithm with eigenval- ues in Region B. Online LDS Losses (Rogion B)
Interestingly, we see that context length / consistently fails in a qualitatively worse fashion - indeed, some of the values in Region A are actually "bad" for q = 1/2. This seems suggest that such eigenvalues can actually cause instabilities with length generalization and are not limitations of our proof- if true, such a fact could be seen as partial converse to Theorem 5. To check this conjecture empirically, we run another experiment where we generate a random LDS of hidden dimension 512 with all eigenvalues in Region B and plot the prediction losses le (MM', TT) for M' from Algorithm in Figure 3 (averaged over random seeds and smoothed). These results confirm that (some subset of) this bad region is indeed what impedes the length generalization capability of spectral filtering.
774
6.30
7
0
0.33
2530
3008
1300
1000
12500
1500
Figure 4. Loss for Algorithm 2 with eigenval- ues in Region B.
4.2. Induction Heads
Next we apply our novel Algorithm 2, which uses two au- toregressive components. Theorem predicts that this algo- rithm should be robust to this bad region of eigenvalues and instead achieve length generalazation for any (symmetric, marginally-staie
So far, we have demonstrated length generalization of spec- tral filtering on linear systems: when trained with a shorter context length of T" is able compete with methods that have access to the full context T (even on marginally systems that can have arbitrarily large effective memory lengths). This length generalization property is most crucial in deep learning applications, in which multi-layer models are stacked (with added nonlincarities) to solve non-LDS sequence prediction task
LDS. We verify this experimentally in Figure 4 --th to be as adversarial as we can, this experiment is run with all cigenvalues sampled from Region B. As pre- dicted by Theorem 6, the second autoregressive component allows for robust length generalization even with context lengths as small as VT.
7

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
As an empirical proof-of-concept demonstrate that STU's length generalization capability extends to this regime, we evaluate it on the induction heads synthetic sequence mod- eling task, which is commonplace in the language modeling literature (see (Gu & Dao, 2023)) and was experimentally shown in (Liu et al., 2024) to be efficiently solved by a two-layer STU. In the induction heads task, the model is required to recall one token (sampled uniformly from a vo- cabulary) immediately after special f flag token; the rest of the sequence consists of the same special blank token, which the model should learn to ignore.
context. As such, this method allows for the convolutional mode during training and inherits all the benefits of STU that are demonstrated in (Liu et al., 2024). For example, the nonlinear selection mechanism of (Gu & Dao, 2023) allows for extreme length generalization on induction heads without prior knowledge of the evaluation length, though at cost to training efficiency, implementation simplicity, and optimization complexity. We reiterate that our goal is not to navigate such tradeoff by modifying the STU model so that it length generalizes on induction heads, but rather to exhibit provable length generalization capability of the STU that comes for free from its natural structure.
The STU architecture we use is composed of an embedding layer, two "tensordot" STU layers with MLPs and ReLU nonlinearities, and an output projection layer (the same as in (Liu al., 2024)) with filters of length 256.
5. Discussion
In review, we first introduced the notion of Asymmetric- Regret as way to describe length generalization through the lens of online learning and regret minimization in games. We then proved that the class of spectral filtering predic- tors naturally enjoys sublinear Asymmetric-Regee thereby cxhibiting length generalization without any change to the algorithm, albeit with some restrictions on the underlying data (i.e. the spectrum of A). We introduced a new variant of spectral filtering which uses autoregressive com- ponents and achieves length generalization which is more robust to the assumptions of the underlying data. Next, we used experiments on synthetic data generated by an LDS to demonstrate the validity and sharpness of our theory and pro- vided proof-of-concep! length generalization experiments on synthetic nonlinear sequence prediction task.
Following prior STU architecture implementations we use no autoregressive components, and so any length gener- alization observed here comes directly from the filtering mechanism itself. We train these models until convergence with a tuned Adam optimizer and various context lengths TV, The vocabulary size set to 4.
Induction Heads Length Generalization
1.05
0.50
Our theoretical results and initial empirical findings reveal that some type of length generalization comes naturally with the spectral filtering algorithm. This result implies that spectral filtering is powerful in its ability to learn the dynamics of a complicated underlying system with long memory - naturally handles the issue of what aspects in a sequence should be memorized for the future and what as- pects be forgotten, whereas many existing methods are hand engineered depending on the specific task. This adds to the already-exciting list of its useful (and provable) prop- erties, including: robustness to systems with long memory and large hidden dimension, efficient training via convo- lutions, optimization convexity, and the existence of good parameter-efficient approximations. Given recent successful applications of spectral filtering as the building block for STU models in deep learning (Agarwal et al., 2023; Liu et al., 2024), it would be valuable to research how to best take advantage of their length generalization capacity at scale - we leave this for future work.
0.85
732
756
738
0.50
evel context length
Figure 5. Accuracies for STU models trained on induction heads task of length I and evaluated on sequence lengths increasing up 7', averaged over random seeds.
Accuracies are plotted? in Figure 5 for evaluation task lengths increasing up to T. As we see, vanilla STU models are able to nontrivially length generalize and occasionally retain good accuracy beyond their training context lengths, though inconsistently. Importantly, unlike algorithms that achieve length generalization through architectural modi- fication, we simply train with filters longer than the train
EEven though the accuracy cannot go above 1, the error bars (1.96 times standard deviation) are still well defined above this value. For example, 7766 at eval length 256 has average accuracy of 95% with error interval roughly [85%, 105%), indicating that most trials achieved perfect accuracy and length generalization.
8

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
Impact Statement
References
This paper is primarily theoretical, proving that spectral filtering learns LDS's efficiently under stronger notion of regret which describes type length generalization. We believe there societal consequences of our work that require specific highlighting here.
Agarwal, N., Suo, D., Chen, X., and Hazan, E. Spectral state space models. arXiv preprint arXiv:2312.06837, 2023.
Anil, C.. Wu, Y., Andreassen, A., Lewkowycz, A., Mísra, V., Ramasesh, V., Slone, A., Gur-Ari, G., Dyer, E., and Neyshabur, B. Exploring length generalization in large language models. Advances in Neural Information Pro- cessing Systems, 35:38546-38555 2022.
Acknowledgements
Flad Hazan acknowledges support from the Office Naval Research and Open Philanthropy.
Bansal, A., Schwarzschild, A., Borgnia, E., Emam, Z., Huang, F., Goldblum, M., and Goldstein, T. End-to- end algorithm synthesis with recurrent networks: Ex- trapolation without overthinking. Advances in Neural Information Processing Systems, 35:20232-20244 2022.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 1877-1901, 2020.
Cesa-Bianchi, N., Conconi, A., and Gentile, C. On the gen- eralization ability on-line learning algorithms. IEEE Transactions on Information Theory, 50(9):2050-205) 2004.
Dehghami, M., Gouws, S., Vinyals, O., Uszkoreit, J., and Kaiser, L. Universal transformers. arXiv preprint 2018
Dosovitskiy, A., Beyer, I.., Kolesnikov, A., Weissenbom,
D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. / 2020.
Gu, A. and Dao, T. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752, 2023.
Gu, A., Dao, T., Ermon, S., Rudra, A., and Ré, C. Hippo: Recurrent memory with optimal polynomial projections. Larochelle, H., Ranzato, M., Hadsell, R., Balean, M., and Lin, H. (eds.), Advances in Neural Information Pro- cessing Systems, volume 33, pp. 1474-1487. Curran As- sociates, Inc., 2020.
Gu, A., Goel, K., and Ré, C. Efficiently modeling long sequences with structured state spaces. arXiv preprint arXiv:2111.00396, 2021a.
Gu, A., Johnson, I., Goel, K., Saab, K., Dao, T., Rudra, A., and Ré, C. Combining recurrent, convolutional, and continuous- time models with linear state space layers. Advances neural information processing systems, 34: 572-585, 2021b.

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
Gupta, A., Gu, A., and Berant, J. Diagonal state spaces effective as structured state spaces. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022. URL https: /tt.nttpss//peeereeiii.e openreview net/ forum?
Murray, K. and Chiang, D. Correcting length bias in neural machine translation. arXiv preprint arXiv: 10006, 2018.
Newman, B., Hewitt, J., Liang, P., and Manning, C. D. The eos decision and length extrapolation. arXiv preprint arXiv:2010.07774 2020.
id-Rjsoj6tsSrf.
Hazan, E. and Singh, K. Introduction online nonstochastic control. arXiv preprint (eXiv:2211.096111 2022.
Orvieto, A., Smith, S. L., Gu, A., Fernando, A., Gul- cehre, C., Pascanu, R., and De, S. Resurrecting recur- rent neural networks for long sequences. arXiv preprint urXiv:2303.06344 2023.
Hazan, E., Singh, K., and Zhang, C. Efficient regret min- imization in non-convex games. In International Con- ference on Machine Learning, pp. 1433-1441. PMLR, 2017a.
Poli, M., Massaroli, S., Nguyen, E., Fu, D. Y., Dao, T. Baceus, S., Bengio, Y., Ermon, S., and Ré, C. Hyena hierarchy: Towards larger convolutional language models. arXiv preprint arXiv:2302.10866 2023.
Hazan, E., Singh, K., and Zhang, C. Learning linear dynam- ical systems via spectral filtering. Advances in Neural Information Processing Systems, 30, 2017b.
Press, O., Smith, N. A., and Lewis, M. Train short, test long: Attention with linear biases enables input length ex- trapolation, 2022. URL https: /ttpiv/wwvv..a//......//... /abs/ 2108. 12409.
Hazan, E., Lee, H., Singh, K., Zhang, C., and Zhang, Y. Spectral filtering for general linear dynamical systems. Advances in Neural Information Processing Systems, 31, 2018.
2108.12409.
Schwarzschild, A., Borgnia, E., Gupta, A., Huang, F, Vishkin, U., Goldblum, M., and Goldstein, T. Can you learn an algorithm? generalizing from easy hard prob- lems with recurrent networks. Advances in Neural Infor- mation Processing Systems, 34:6695-67000 2021.
Hazan, E., Kakade, S., and Singh, K. The nonstochas- tic control problem. In Kontorovich, A. and Neu, G. (eds.), Proceedings of the 31st International Conference Algorithmic Learning Theory, volume 117 of Proceed- ings of Machine Learning Research, pp. 408-421, San Diego, California, USA, 08 Feb-11 Feb 2020. PMLR. URL http: / http://pocceeeeneeeeeeeee//essee www.inngsmmrr....mmm prwss /v117/ hazan20a html.
Smith, J. T., Warrington, A., and Linderman, S. Simplified state space layers for sequence modeling. In The Eleventh International Conference on Learning Representations, 2023.
Hazan, E. et al. Introduction to online convex optimization. Foundations and TrendsS in Optimization, 2(3-4):157- 325, 2016.
Tay, Y., Dehghani, M., Bahri, D., and Metzler, D. Efficient transformers: survey. ACM Comput. Surv., 55(6), dec 2022. ISSN 0360-0300. doi: 10. 10.1145/3530811 URL
Hou, K., Brandfonbrener, D., Kakade, S., Jelassi, S., and Malach, E. Universal length generalization with turing programs. arXiv preprint ar arXiv:2407.03310. 2024.
https:/ /doi: wwwoorg//.00. 0 11 14/14//335 45/353081.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, I.., Gomez, A. N., Kaiser, t.,, and Polosukhin, At- tention is all you need. Advances in neural information processing systems, 30, 2017.
Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvumakool, K., Bates, R., Židek, A., Potapenko, A., et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-589 2021.
Yehudai, G., Fetaya, E., Meirom, E., Chechik, G., and Maron, H. From local structures to size generalization in graph neural networks. In International Conference on Machine Learning, pp. 11975-11986. PMLR, 2021.
Kaiser, L. and Sutskever, I. Neural gpus learn algorithms. arXiv preprini arXiv: 0ee.:///1100226 2015.
Zhang, Y., Backurs, A., Bubeck, S., Eldan, R., Gu- nasekar, S., and Wagner, T. Unveiling transformers with lego: a synthetic reasoning task. arXiv preprint arXiv:2206.043000 2022.
Kazemnejad, A., Padhi, I., Natesan Ramamurthy, K., Das, P., and Reddy, The impact of positional encoding on length generalization in transformers. Advances Neural Information Processing Systems, 36, 2024.
Liu, Y. L., Nguyen, W., Devre, Y., Dogariu, E., Majumdar, A., and Hazan, E. Flash stu: Fast spectral transform units. arXiv preprint 4409 10489, 2024.
10

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
A. General Length Generalization
In this section we introduce a general algorithm which we will use to prove length generalization for both Algorithm and Algorithm 2.
Algorithm 3 General Spectral Filtering
1: Input: h > 0, L 0, r > 0, functions pr(.), vectors Vi:k-
Initialize M, = 0 for i E [k]]
2: for t= 1, ..., T do
3: Compute and predict
Jr = 11-p(ut-iill 1:1) + Σ L
4: Observe ye. denote (M,,, L) = -liee- - yell² and update and project update and project onto the low Frobenius norm ball
M M tn (ase((M
M4+1 Proje (Alett),
where K,, = {M s.t. || S r}.
5: end for
Our workhorse theorem is presented below. We will use this theorem to prove length generalization for our special cases in the following sections.
Theorem Suppose y evolves as a noiseless (A, B, C, CY-LD and the input u(t- 1):0 is such that ET-1 (T - t)u, E
(2I[TII[BBI\TT)) Let k L, r, {u. pc(.), and l((-) all be defined in Algorithmm 3. Suppose {v, J is orthonormal with le:ll S (T). Suppose that Pc(-) is such that there exists some function h((), constant & >> O, and some M E Krr such that
T
8, M
t-
yt (11 =
M
the
ui 4-1000%
Ut +
CA
where
T
M
U4 14-11--100 $ ||[|||
i=k+1
and
max (h(a)a -1-1 (M(a)at-1-11 - a T- -a) <
1
a(A)
71/4'
Then if M are the iterates of Algorithm and T 2 (41 (T) (TT)/|[[]]]] B1I)
min Σ ELMM,L)
EK, E < (122312,2 (12x3/2,22og (T) +T) 81|1(1111113) VT.
The proof of this theorem requires several technical lemmas which we present and prove in the subsequent subsections. In Lemma 8 we essentially prove the standard result showing that Online Gradient Descent implemented in Algorithm 3 achieves O (T) regret. In Lemma 9 we prove the more nuanced result which shows that the optimal M which minimizes the loss on the full T-length context achieves length generalization in the sense that it achieves small loss even when only allowed to use context length Combining these two lemmas gives the proof of Theorem 7.
Proof of Theorem 7. Let
M
Σ ((M,TT M M..
min

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
and observe that
min M EA.
((M" L) S Σ 4(M7, L).
(8)
Combining this with Lemma 8 and Lemma 9, we conclude
T
(eM,) &
min ER,
()
OGD Regret Lemma
L) log
Eq. 8
(M + (12A (1243% 1101
Length Generalization Lemma 9
Σ (1N,,))+(122)7)7 log()) + E
min
Definition of M
A.1. OGD Regret for Generalized Spectral Filtering
Lemma 8. Suppose the inpul u1a satisfies ||ue|12 S 1. Suppose the true oulput yt evolves such that for some polynomial Pe (11 there exists some M E Kr,
T
+ yt = P-
M 14-1:00%
f=1
andfor
T
EM,T
def
M 40-1.0
1=k+1
we have ||m,TT| S 1. Further suppose U....., satisfy || I a (T). Let
(, L) del live Pt (V
Σ
Man-
i=1
Then if M are the iterates of Algorithm 3
T Σ
T
Le(M',)
Σ ((M,LL s /2 M
min
P (T)(T)
Proof of Lemma 8. This proof near copy of the proof in (Hazan et al., 2017b), the difference is that we derive several equations that we will use later and we handle the varying context length.
Let G = max ( I)]l and let D max McKK. IIM - M2ll. By Theorem A.1 from (Hazan & Singh, 2022).
T
T
Σ
44M L)
min Σ
4(M,L s GDVT.
M"EKr 1=1
2
Therefore it remains to bound G and D.
First we bound D. By definition of Kr,, we have that for any M E Kr.
|| S
12

---

and Provable Length Generalization in Sequence Prediction via Spectral Filtering
Therefore, also have that
|M S vkr.
Therefore
def
M --1ll S 2Vkr.
max M, ERr
Next we bound the gradient norm G. Using the definition of Krr,
max max |Milll S r. MEK. (E(M]
We bound the gradient norm as follows,
k
VM, ((M, = 1|2
M tue u, 1:04; + Em,T
Mj U4 1:t
11- 1.
(ut (11-1=-100) I
k
< 2
|| 10 + |m + Σ
Millll 1s- Iba 11s/l
|| r. |ا51
2m
< 2 (1 + Em
max MEK,
|M
11 -1u//1?
< 4kr lT'.
Putting everything together we have
T Σ
( 4kr Akr 18g(7) (2Vkr) VT
Σ 4MM, L)
min M EKC
4(M", s
p 1/2 (TVT)
A.2. Length Generalization on the Best Optimizer in Hindsight
Lemma 9. Let input ((--1): {uikee pc(-), and (,M,, L) all be defined in Algorithm 3. Suppose the input u(t-1):0 is such that Et- t. 2 [ T, {e is orthonormal with ||ua|/ I log" (T), and that there exists some Mine such that
T
t
y/ (1)
=
M
U4 1:00/ =
M U4 u
Bu -i f1
where
T
M Mine U1 1--1---01 S ||C||
i=++1
-
(1 -1 s
1
max a(A)
71/4
Let
def M arg min MEK,
((M,T).
Then for T 2 (4k: log (T)] the loss with context L well approximates the loss with context T Mt.
&MM,, - s BICTT
13

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
The proof of Lemma 9 requires key helper lemmas which we develop in the following subsections. The first is Lemma 10 which establishes that when yı: evolves as noiseless LDS and if the input u1:t is sufficiently well-conditioned, then the minimizer for Din & (M) approximately recovers a collection of matrices (we denote M!") which is generated by the true linear dynamical system. The second key helper Lemma is Lemma 11 which establishes that an algorithm which uses the collection of matrices that are generated by the true linear dynamical system, i.e. M able to achieve small loss even when restricted to a small context-length L << T. The proof of Lemma 9 combines these two insights to establish that this implies that the minimizer for Σ ( T) also achieves small loss even when restricted to small context-length
Proof of Lemma 9, First we show that Muue is [|C | (T) approximate minimizer to Et= (M,,T). Indeed,
T
Σ
M(Muue Muee T)
Σ
bt
Pt (11-1.1)
M 4411001/1
i=1
T
T
M
true Up 1:00:
x=
|| /T.
By assumption Ei= (T t)ue?? 2 (2I[C]] IT) Therefore, by Lemma 10 with ||C||||||/vV we have
Mj E B BImmBn/ (M
Since we assumed T 2 (4k
we have
|CI|IBI\VV < 1C1P1111/((4T//440011)
Therefore by Lemma 11 we have
T
Σ L(MG,L) & 4/C01/IBBIVT.
Moreover note that Combining these we conclude,
0 T) ((MTH, = 11811111112. z SICTPIBBBTV.
T
T
G(M;.D)
Σ ((M,, &
1. MINIMIZATION IS RECOVERY
Lemma 10. Suppose ΣT- (T t)u,? łn2 2el and (urkem orthonormal. Then there unique point M which minimizes the function Ex (cM, from Algorithm 3. Moreover, suppose some k satisfies
Σ 4(M,T) < ?.
Then there is matrix Eas such that || I and
M M EMg
Proof. For convenience, let X, be the kdd, dimenssinnl vector which stacks the filters.
U4 -1-1:t-701
W4-1:00 u
-
U 1:022
X
U4-1:t 2%
1:0 R%
14

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
where the second inequality holds since we only consider de x and let Y V/+ (1())-1:1). Let express the loss as
S T. Assume k is written as M [M
M2
[
Y/ Yr] and X [ X₂
Xr]
Then we can
S(M) def
(M,,T) |Y MX
Note that this function is twice differentiable and
(MMM) = XX..
Therefore, if Amin (XXT) 2 we have that S(M) is p-strongly convex. Then if M is the optimum of J(M) we have
S(M) 2 ((M) + u 2 IM - M or equivalently, JM - M < - (((M))((M()).
Now suppose & is such that f(M) e.. Then since f(-) 2 0 we have
|| - M S 26²/u.
Therefore we can write
M M + Es. where | || I 2e² 26²/U.
Next we must understand the eigenvalues of xx and how they relate to the input ura For notational convenience, let ura and let D2 denote the block-diagonal x T matrix
D3 def
O O1-
1
Tt]
Finally, let
U1
U2
V
E Tmx1
Uk
Then we have X, = (1&0U)) V and we observe
T
xx =
XXX,
Σ
((4 (L.D))
t=1
Σ
(4.BUDUU)
1=1
ED EDIJUT.
= 4
1=1
Observe that
T
Σ
Dj = diag ([1 2 T)).
t=1
Using this we can further refine
T U
T-1
Σ
Dz
UT
Σ (T t)um
By assumption, this matrix has minimum eigenvalue bounded below by 2e. Therefore Amin(XX 2 2e. Plugging this value in for y in Eq. 9 concludes the proof.
15

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
A.2.2. UNIFORM LENGTH GENERALIZATION AROUND LDS GENERATED SOLUTIONS
The following lemma shows that any k in an (appropriately defined) e-ball around M obtains length generalization in the sense that it achieves O( D(VT) L-context-lengthh seateex--engthh-lmiiiee limited loss Σi= 4x(,; L).
Lemma 11. Suppose Yt evolves as a noiseless (A, B, C, 1) with input un. Suppose pe(-) and M is such that
Vt Pr (V
M 1:00/
M Uu
CA'((A) -1-
1=1
Suppose for a given l > 0,
||||]| B|
M Up 1-1--100 $
T
#=++1
Suppose
max (h(a)a- - - -1- s
1
a(A)
71/1¹
If
8 I 1 |
4m T log"(T)
then have for any M (M(Me
T L) < 4|CT)11BBRVT.
Proof of Lemma 11. Let M Mi + EM,, where |Msll I By definition,
k (M + EM), ur 11-1:0-1011
mm + EM, L) = 11 (P
= =11ve (3
M mu 1:1-12
EM. 11-1--
I 11ye - pe(y 1:1) Σ M ur 1: 11
+ 2/|yv - Pe 11)
Σ
M Ur 1.U Σ
EM, Uy -1-
1=1
EM, U4 1
Observe that
E M4 11
EM - kd (TT
For the remainder of the proof we work towards bounding I/ve - Pr(Vi-1a) Et_ M We re-
place y/+ (e() with Er M and we replace Σ M 1 with ΣTr -
16

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
El M U1 - L3 get
T
T Σ
T
live (11-1111))
M 1:t 111 =1
Σ
M
1-0%/
M
1:t-
M 1:t Ub
112
1=1
k+1
T
M tiee 11-1 11-1:t-L) 1)uu11
T
+
2|
M (
Σ
M
x++
+
||
M
W4
f=++1
- assumed to be at most ||C||| /T and so we now focus on bounding the Next we note that || E/ M. norm:
T
M (we-1:0 - the 1.)
(10)
i=
Towards bounding Eq. 10, assume
b so that
T
M
(ut-1:0 1:0 Ur 1st 1.)U3-
Σ
Cu--())
1-411
Σ
Σ
un-e----
-+
Then
Σ
CA'H(A)uu---ll) < max jE|dal aaa((a))
Σ
[CBB] wi-l
+1
< max
Σ
a'M(a)]CCIIB].
Next we have
1-4-11 max aA))
T-L
Σ d'h(aa)
s M(aaa 4--11 Σ
i=1-4+11
a T- L+1
= =((aaa-08
1 a
S T-1/4
where the last inequality holds by assumption. Therefore Eq. 10 is at most
M tree (we-1:0 w1-10-1)el <
|| 1/4
Then we have
|C
|C
|C
|| B1
1y, - Pe (P(
M Mimen Uq 1:1 1
2
T1/2
T3/4
72
T/2
17

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
Finally conclude
B
||
1/2 [B12)
((b1og(T)) + (ko ( 2
m LM,
T
71/2
||
71/2
where the last incquality holds since we assumed
ICP11 8 S 4m T1/1 (T)
B. Length Generalization for Vanilla Spectral Filtering
The proof of Theorem 5 ultimately comes from Theorem 7 and its proof in Appendix A. Theorem 7 abstracts the necessary assumptions needed to obtain length generalization guarantee. In Lemma 12 we prove that Algorithm satisfies these assumptions.
Proof of Theorem 5. By Lemma 12 and the assumptions made in the statement of Theorem we may apply Theorem to Algorithm to get that
Σ L(M L)
min MiEKii
Σ 4(M" T) s
log(T) S|C|I) VT.
Lemma 12 (Length Generalization for Vanilla Spectral Filtering). Recall that in Algorithm 1 we define
def (a 1)
T-IJTRRTT ERR
Ha
and HT-1 Jae[o.1] PaPo do and let .1,..., -1 be the orthonormal eigenvectors of HT with eigenvalues F1,...,0T-- Algorithm is equivalent Algorithm with the following:
(a) pe (v(---1a1) V1-1
(b) 11 =1
(c) ni- = (0, 1/4 0111)-11) for = .,....T
Define Muee as follows:
Mirec CB,
def
and
da
Minee def
2
0i-1 Di-itlan (Cn.B,))
1/4 T
Then the following properties hold
1. For (((A) = and &
6, Σ
91 Pe()
Mine ui
[m1
18

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
2. y1 (1 = E/= "
3. For k = Q[[og[[d
T
MM
u1 I
c/T.
im k++
4. For any i [T]
| S ||C|||
5. For any i (T). ||si|| S log(T) and (etry are orthonormal.
6. Finally if the spectrum of A lies in the interval
0,1 ITg
2(L 2)
27/544
then
max (Ih(a)a -1-a--Lt33 - aa) a(A)
1
T1/4"
Proof. Points (a) (c) are evident by definition of Algorithm 1. Now suppose evolves as an LDS. By definition, there
exist matrices (A, D, such that
y/2 CA
CA--1BuL-ts
Buc-
where assume D I and A is diagonal without loss of generality. Let 01,..., Od, denote the eigenvalues of A. and let Mr:0 be the din x T (padded) matrix u1.0
Wt
W4-1
0]. Then we have
Vt Vt-1 Σ CA Bu
Σ
CA - Bu--1-
1=1
=Cuu-1 EC ( Bu------
1=1
We pause here to note this proves (1). We continue rearranging the equation to finish the derivation of (2).
V/ 9t-
CB
Σ
CA' 11-1) Bu--1-i
ds
1-1
=CBu-11 +
Cene
Σ
(a 11
u1-1-t
n=1
1=1
da
CCB4-11 +
(,, ) 2):0/a.
n=1
Observe that
T-1
0:0 =1.
Using this we have,
da
yt
V- CBB4-1 +
(C,, C,, (
n=1
da
T
=BBu-1 +
(C,, B] (1(22))
Eoro pon
n=1
-CBu-11
d Pa. (Cn )
19

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
Recalling the definition of Muse and vi = 01-101-1 we therefore have established (2):
1/4
yt V1-1 M1 u(t (1-1))061
M M u11-1):0%
Next we aim to prove (3). We consider
Σ
M
tue Wit 2):0%
i=b+1
By Lemma 13.4 in (Hazan & Singh, 2022) there some universal constant d' such that,
10 Hal S e'T² exp(-i/log(T)),
max eE
So,
MM
u(1-2):00411 = Σ
0:11 Pi_iMan (an (u) ) 2):0 (0i-10--1)
1/4 T
1/4
n=1
da
Σ
i Ma (C (1t
$ d ( 1) copp-((111//og(7))))..B.. 1
//2 (xl4T"/2exp((101 ()0_)////[(()))]]]]]1111
Therefore,
Σ
M. mue uu u1-10:0011 I log())/
k=++1
Therefore as long
k 2 log
then
T
Σ
M tre u1-11:00:1l S T
i=1+1
Next note that the proof of (4) that ||M!
B|] is proven in Lemma D.1 of (Hazan al., 2017b). Similarly, the proof of (5) that ||w:1| < log(T") is proven by Lemma 13 from (Hazan al., 2017b). Finally we prove (6). Since T((a)= = and & = 1, we have
(16(a)a--1-1111 a T- a)
max I. 2- a T-+1). a(A)
(11)
a(A)
To bound Eq. 11, consider the case where a is bounded away from 1. Suppose a 8, then
p plog(T) (T)
(1 -1-88 1) S TF
log
1-8 2
L - 2
Observe that for 8 E [0, 1], (1/(1111/111111111 6)) 2 6/2. Therefore, if
2p log( (T)
8
we are guaranteed that a- < 1/TP, Next consider when is very close to 1; suppose
2 1
TsT for < 1/2. Then
using that (1 xx)8 > 1 2qr for x E [0, 1] we have
T-1 2 1- 1
T-1-1
2 1
L-1+1
=
1 o
T-L+1
< 2
T T-L+1 2
TrT <
TrT
TFT
TP
20

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
Plugging in p 1/4 conclude that
for any a E 0. log(T) 2(L - 2)
a 2 - a T-bt1) S T-1/4
U
2T
The following lemma comes from (Hazan et al., 2017b).
Lemma 13 (Hazan, Singh, Zhang). Let (aj 6ÿ) be the j-th largest eigenvalue-eigenveetie pair of the T x T Hankel matrix. Then,
log(T)
11 S o
1/4
C. Length Generalization for Spectral Filtering Using Two Autoregressive Components
The proof of Theorem ultimately comes from Theorem and its proof Appendix Theorem 7 abstracts the necessary assumptions needed to obtain length generalization guarantee. In Lemma 14 we prove that Algorithm 2 satisfies these assumptions.
Proof of Theorem 6, By Lemma 14 and the assumptions made the statement of Theorem we may apply Theorem to Algorithm to get that
T
T Σ ((M" v (128"21C1) +ICCIPIBBB VT.
2
4(M', D)
min MeKeeel
Lemma 14 (Length Generalization Using Two Autoregressive Components). Recall that in Algoritlum 2 we define
Pa.r del (a (a-1)) 1)
a EERT
and and Nr = Saeio.1) Po. and we let .1.... δT be the orthonormal eigenvectors of NT-2 with eigenvalues
G....., 0--2. Algorithm is equivalent Algorithm 3 with the following:
(a) pr (1)-11111) -2tt-1 - 1/--2
(b) 01 = e1, U2 = and for i 2 3, = (0,0,0;-20--
Define Mue as follows:
M
def CB,
Mirue def C(A - -2)B
for 2 3.
da
Miuue def
ai -1 1/4 (aa))
(Cn
Then the following properties hold
1. For h((A) = (A - 1)² and E
E, Σ
fs
91 pe(()-1a))
Minec un
+
Σ
Cu
[m1
21

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
2. y1 (1 = Ei= --11%
3. For k O(llog(To [[oo((Tdal(C]11111//))
M. u1111: I c/T.
1+
4. For any i [T]
|M S |||||||||
5. For any i [T], |elll Tog(T) and {ux (etrr)t are orthonormal.
6. Finally if the spectrum of A lies in the interval
log(T) 0,1
2(I - 2)
271/41
then
max (Ib(a)a 1-----11111 -1-2 (1 - 1) s T1/4 a(A)
1
Proof.
Suppose ye evolves as an LDS. By definition, there exist matrices (A, B, (, such that
V1 Σ
t=1
where we assume D and A diagonal without loss of generality, Let 01....,,a denote the eigenvalues of A. and let Ur:0 be the din x T (padded) matrix un.0
[we
14 0]. Then have (1):
14-1
Vt 2yr-1 y CBu-1 C(A 21) Bu,
Σ CA 2A + B)
-2
Let o1,...,, Oda denote the eigenvalues of A. We observe the following equality:
3-3
3
d
Σ CA2 24 1)
Σ
(ann - en Bu4-3-i
1=0
R=1
da
1-3
(Cene B)
Σ (a 1)²44-3-
1=0
(C,,B.) u(t-
Observe that
T-2
Σ
T. = 1.
1=1
Using this we have,
Σ CA' - 2A 1)Bu,331
Σ
(C,, u(1-3))0aam
T-2
E Pan
(CnB
U(t-3330
d
ti Pon (Cn BT))
u(c-s),00
m=
M uct-1)o02z
22

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
Therefore have established (2). Next aim prove (3). We consider
Σ
M
"(o-1):0%
1=++1
Combining Lemma 15 and Lemma 16 gives that there is some constant d' such that,
max ac
( Mal S deep(-i//loo(TT)
So,
AA
M
mo u
1(1-1):001]
=
0 i- 8
1/4
ii- ( (1/11/111
n=1
aan (C ) 2
n=l
da exp( - 1isp-((i-1)/oog())111311
B||-
Therefore,
Σ
M (1-1)):0111 $ "d [ [B]-
k=
Therefore as long as
2 (log())log log
then
T
Σ M uit u(r-1):021 S T i=++1
To prove (4) we note that the statement is obvious for i S For 3 the proof from Lemma D.1 of (Hazan al., 2017b) directly applies due to Lemma 15. Next, Lemma 17 proves (5). Finally prove (6). Next, Lemma 17 proves (5). Finally we prove (6). Since we have h(a:) = (a 1)2 and 2 2.
max (I(a)aa-3( - -f af -) max {(1 (1-a)a+-3) -- a -- a(A)
(12)
a(A
To bound Eq. 12, consider the where is bounded away from 1. Suppose a - 8, then
PT)g(T)
(1 13--3- - Tp log T-8
L-
-)) 2 5/2. Therefore, if Observe that for 8 E 1), log(lo(1 (1)()18)))
2p log())
3
we are guaranteed that a 1-3 < 1/T", Next consider when a is very close 1. To ensure that Eq. 12 is bounded by 1/T2
we only require
TF.
Plugging in p = 1/4, we conclude that Eq. 12 bounded by T 1/4
Oh E 0,1 ITg
1
1
for all n E [dA].
2(L - 3)
T1
23

---

Provable Length Generalization in Sequence Prediction via Spectral Filtering
C.1. Properties of the Hankel Matrix for Two Autoregressive Terms In Algorithm 2 define
fla def (a - 1) a at1 T ER?
and
NT =
oe Mata da.
In what follows we present and prove several lemmas needed for the proof of Theorem 6.
Lemma 15 (Properties of Nr). For any E [0, 1] and i T,
max T pal S 61/40,' ///4 aE[0,1]
Proof. We have
JAETOLL (o.Ta) da = T5 ( HaPla de (JeenonfaaRia
= NrØ: =
Next we observe that for fw(a) def Twa Indeed.
where w any unit-norm vector, we have that fw is G-Lipschitz on [o, 1].
fa(a)
- (a - 1)a
d
Σ wia+-1
da
2(aa 1)a
Σ wiatt1 1-1
Σ - (--))aaat2
+
Σ
w;a'1
(a (a- 1)3
1=2
i=1
1 a
S 2(aa 1)¹
Σ ia
+4
(a (13
1 a
1 a
1 l-a7
1- Ta + (T - (1-1)a
+4 1111-00 aT
=1(1-0) a
2
2(aa 1)1
(a- 1)3
1-a a
(1 (1=
2 0² (1
Ta T-1 + -T- 1)a²) 4 a² (a-1)
< 2244=0
Consider any non-negative L-Lipschitz function f that reaches some maximum value Jmax over [0, 1]. The function f which
satisfies I-LLpschiizzesss, attains 9mmx (f) and also has minimum possible area A(F) def Sacjouy fa)d is
Lax max {gmax L(a - a())))))0) for a E [a",
for a E [0, a*)
(a)
La,
for a E [0, [0,a"]
- aa), for [a* a 9
Imnxx
0,
for E (a* +
Indeed, any oscillation away from this piecewise linear function would either increase the total area or violate the Lipschitz constraint. For this to be valid construction we must have La Gmax and therefore the minimum corresponding area is
A()) = (00==/oa (((adda 1 (aa") + (9max/ L)axx
9
24

---

3 Provable Length Generalization in Sequence Prediction via Spectral Filtering
And therefore for any function we have Imax (f) VLA(J). Using this for So,(a) have
max (0) ma) S Vo J (0, do voo.,
max e
[a)
ac(10,]
We conclude by noting
max e
( Na
max
(0, 1aa2 S 61/40!44 1/4
V <e(00,1)
Lemma 16 (Adapted from Lemma E.2 from (Hazan et al., 2017b)). Let oj be the j-th top singular value of Nr. Then for all T 2 10 we have
0 S min K.Koo///og
where c ex x0 11.79 and K & 10 is an absolute constant.
Proof. The proof provided in (Hazan et al., 2017b) applics directly to Nr with only one necessary modification to bound the trace. Observe that we have
(Nr)
(a- 1)2aat5-2200
JEE/U,1]
JaEja.1
a'ts - + -
24
1) 1]++j+2((++++)
Therefore,
24 oj tr(Nr) (2i 1) () 2) + 3)
24
3
1
3
(2
15
2
The remainder the proof is an exact copy of the proof of Lemma E.2 with 3/4 replaced by 3/2.
Lemma 17 (Controlling the & norm of the filters). Let (arg, Φz) be the j-th largest eigenvalue-eigenvetto pair of Ny. Then for T 2 4,
log T 1/4
115 s 0
Proof. This proof is a copy from the proof of Lemma E.5 in (Hazan et al., 2017b) with only one noted modification. We note that E' as defined in their proof is entrywise bounded (for T 2 4) by 24/T < 2/T (which is the stated bound they use for their matrix of interest). We also must show the base case is true for To = instead of To = 2. We have
[N1/112211 12-1
sup
||N
2111
S
(N1/4)
<2
a:||a]|aa $
+
We note that tighter result is actually true for Ny in that |10 because we don't leverage it for a tighter result overall.
0
log T 0
However, we omit this statement and proof
25


Reviews:
[{"review_id": "zVgpu1ITna", "reviewer": "Reviewer_BkYk", "summary": "The authors study an online sequence prediction problem where the sequence is generated by a time-invariant linear dynamical system within a class of spectral filtering predictors. They introduce a notion of regret between spectral filters that use context length $L$ and the full context, i.e., length $T$. Two algorithms are given to learn spectral filters with limited context and their regrets based on the best possible predictor with full context is shown sublinear, roughly of order $1/\\sqrt{T}$. The first algorithm uses a single autoregressive term ($y_{t-1}$) and the learning guarantees require assumptions on the spectral properties of the ground truth linear dynamical system. The second algorithm incorporates an additional autoregressive term ($y_{t-2}$) with a different spectral filter to have robust estimation even without the spectral assumption.\n\n### Update after rebuttal\n\nI have increased my score following discussions with the authors, assuming they will follow through on their commitments to (i) provide a deeper discussion of length generalization in this work and the related literature, and (ii) highlight the notion of regret and the $L \\ll T^{1/4}$ case, as described in their rebuttal.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your thoughtful and detailed review!\n\nQ1 (L vs T) \n\nIn the paper we distinguish between L and T, where L is the context length and T is the overall sequence length. It is possible to take L=T. You are right that $\\phi_i$ has size $T$ but we only allow ourselves to look at $L$ previous inputs and so there is indeed a dimension mismatch if $L < T$. The way we deal with this is by zero-padding the inputs. Specifically, the matrix which stacks $u_t, \\dots, u_{t-L}$ would instead stack $u_t, \\dots, u_{t-L}, 0, \\dots, 0$. We state this on page 1 under ``Our Contributions\" but we can make it a larger/more-clarified point.\n\n\nQ2 (Broader Scientific Literature) \n\nThis is a great point, and we can give an answer, which we think will improve the paper. The reviewer observes that often in length generalization, the predictor is only allowed to learn/train on short context length, and then predicts on long context length and, importantly, in order for the prediction to be correct, the algorithm must make use of the full long context. In the online learning/regret setting the analogous setting would be to restrict the learning algorithm to context length $L<T$ when making gradient updates (ie keep the algorithm in our paper as is) but to measure its performance when making predictions on the full context length. We agree that we should include this notion of regret in our paper. Note that our theoretical results immediately apply to this setting, since the spectral filtering predictor is only given more power. Indeed, the regret bounds provided in our paper would hold for this notion of regret and, furthermore, they would be stronger-- they would hold without any assumption on the spectrum of $A$ with respect to $L$. Of course -- the above works only if the signal comes from a linear dynamical system with the properties assumed in the paper. We will also include a small discussion on which signals we believe would distinguish between these two notions of regret (i.e. when is our original notion of regret too pessimistic for an algorithm to succeed and when must we move to the notion where predictions use the full context?). \n\nEssential References Response\n\nWe will cite [1] as a practically relevant paper, notice our treatment is theoretical and in a broader setting of sequence prediction for linear dynamical systems, not necessarily language. \n\n\nMain Weaknesses Response \n\nWe suspect the reviewer will have a different opinion in light of our clarification of the above theorem and the fact that our results apply to that setting. However, we are happy to emphasize further that our paper is a theoretical one and considers length generalization for general sequence prediction in dynamical systems, rather than an empirical paper on methods that are useful for LLMs to length generalize.\n\nOther Comments\n\n1. We completely agree and will change this phrasing.\n2. Algorithm 1: projection can be applied to any convex set K, but the most common one (and the one we use) is with $K_r$ for some Euclidean diameter bound r.", "claims_and_evidence": "I leave the discussion of the technical results to \"Theoretical Claims\". The experiments in Section 4.1. supports the main technical results on two algorithms presented and convincing. The claims in Section 4.2. on STU is not particularly detailed or convincing.", "methods_and_evaluation_criteria": "The experiments in Section 4.1. is well-suited for the main technical claims of the paper. The experiments in Section 4.2. is to relate the findings to spectral transform units and makes sense to see how the theory extends to these architectures.", "theoretical_claims": "There seems to be a minor issue in the algorithms. $\\phi_i$ are eigenvectors of $H_T$ which is of size $T x T$. Hence, $\\phi_i$ has the size $T$ whereas it needs to be of size $L$. Could the authors clarify how to get spectral filters of size $L$? Is it just simple truncation? As far as I checked, this is not addressed in the appendix as well.\n\nI have not checked the correctness of two theoretical claims.", "experimental_designs_or_analyses": "Experiments in Section 4.1. seem valid with a good design to check the main technical results. Experiments in Section 4.2. are unclear and I am skeptical towards the analysis provided by the authors. There are no details regarding how the experiments are conducted, including the supplementary material.", "relation_to_broader_scientific_literature": "I believe the definition of length generalization used in this paper does not necessarily match the the notion of length generalization in the broader scientific literature, especially the literature on reasoning.\n\nIn this paper, the authors have a task in which they are able to statistically solve with a shorter context length than that of the full sequence. This is atypical in reasoning tasks such as addition, multiplication etc. where the part of the context only gives partial information for the final output. Therefore, in these settings, length generalization refers to the ability of models to apply a certain algorithm learned from shorter context windows to longer sequences. An example would be a model that has been trained in 3 digit summation that generalizes to 5 digit summation.\n\nI believe this distinction needs to be clarified and presented better in the paper. It is unclear how much of the interest in length generalization relates to the setting authors has.", "essential_references_not_discussed": "I don't think the related length generalization literature is discussed in depth in the paper. See [1] and references within:\n\n[1] Anil, Cem, et al. \"Exploring length generalization in large language models.\" Advances in Neural Information Processing Systems 35 (2022): 38546-38556.", "other_strengths_and_weaknesses": "1. The strength of the paper is that it proves a very curious statistical result. This technical contribution seems original and conveyed clearly.\n2. The main weaknesses is that the paper is presented around the topic of length generalization but my judgment is that this is very misleading. Therefore, I suggest the authors to revise the manuscript, clarify the relationship to the length generalization literature (if there is any) and write a paper that focuses on their technical result.", "other_comments_or_suggestions": "1. The definition of context-length for an online predictor needs to be clarified. The wording L167-170 is a bit misleading. I believe the form of the predictor is such that it depends only on the previous L timesteps but the choice of predictor is of course dependent on all the trajectory.\n2. In algorithm 1, do you project to $\\mathcal{K}_r$?", "questions_for_authors": "1. Could you explain my question regarding $\\phi_i$ that is in “Theoretical Claims” section?\n2. Could you please respond to the comment regarding relation to the broader scientific literature.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TIm9rHvu23", "reviewer": "Reviewer_9Uxb", "summary": "The authors consider the problem of length generalization in sequence prediction, i.e., whether online time series prediction algorithms can learn long-range dependencies using only a short context window during training. Despite its importance in areas like LLMs, the current literature offers few theoretical analyses and guarantees.\n\nThe authors introduce a new regret metric that compares the performance of a short-context learner against the best predictor using a longer context. They highlight spectral filtering algorithms as strong candidates for theoretically-provable length generalization and adapt them for short-context settings. In this setting, they derive theoretical guarantees for Asymmetric Regret in LDS under specific spectral conditions on the system matrix A. Additionally, they introduce an alternative spectral filtering method which uses two autoregressive components and has similar regret bounds but with much weaker constraints on A. The validity and sharpness of these bounds are demonstrated through sequence prediction experiments. Finally, they provide a proof-of-concept experiment on length generalization in nonlinear tasks, using a spectral filtering-based deep learning architecture.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your thoughtful and detailed review!\n\nQ1 (noisy setting) \n\nOur theorem extends to the case of stochastic noise with bounded variance. To extend to the case of adversarial noise, the norm of the allowed noise must be bounded with inverse to $T$. We present our results in the noiseless case for simplicity of the presentation and proof, but we can happily provide a corollary or note on this. Note that our theorem is presented in the online regret-minimization setting with respect to the best spectral filtering predictor in hindsight. This predictor gets $O(\\sqrt{T})$ regret wrt the best linear dynamical predictor for *any* signal, regardless of the noise (shown in Hazan, E., Singh, K., and Zhang, C. Learning linear dynamical systems via spectral filtering. Advances in Neural Information Processing Systems, 30, 2017b). \n\n\nQ2 (Section 4.2) \n\nWe think of 4.2 demonstrating that while our theory applies to LDS, it can be more widely applicable even to LLM tasks. It is a proof of concept, and we don't make a strong claim here, we just thought this will be useful for future scientists to explore. We are willing to remove it, the paper has a lot of results.  We are also willing to include benchmarking from other models.", "claims_and_evidence": "The theoretical results in this paper are presented in an understandable and convincing way, and they are clearly supported by Figures 2, 3, and 4.", "methods_and_evaluation_criteria": "The methods and evaluation criteria make sense for the problems discussed, though I wonder if Figure 5 should be zoomed out a bit more so the reader can see the whole confidence intervals.", "theoretical_claims": "I briefly looked at the proofs in sections A, B, and C in the Appendix, and the reasoning made sense to me. I am not an expert on this topic, though.", "experimental_designs_or_analyses": "The experiments supporting the theoretical results provided by Theorems 5 and 6 are well-executed and sound.\n\nI am not entirely convinced of the significance of Section 4.2, aside from vaguely motivating a future work direction about length generalization via STUs. The section does not directly use any of the theoretical results derived earlier in the paper and, as far as I understand, demonstrates that a deep learning architecture based on spectral filtering exhibits some degree of length generalization. It is unclear to me how one should interpret this result, as it is not given in comparison to other deep learning architectures (RNNs, Transformers, SSMs..), which presumably also have some generalization properties.", "relation_to_broader_scientific_literature": "This paper is a clever and important contribution to the theory behind the long-range memory mechanisms of sequential models, which is subject to many empirical studies. The authors provide strong insights into the theoretical guarantees of length generalization of spectral filtering algorithms in the case of linear systems and suggest interesting future work directions for non-linear systems.", "essential_references_not_discussed": "The literature is sufficiently covered.", "other_strengths_and_weaknesses": "See my comments above.", "other_comments_or_suggestions": "I believe that the STU acronym is currently not defined in the text, and I think it would be useful to include a sentence in Section 4.2 explaining what STUs are.", "questions_for_authors": "1) Your theorems assume a noiseless LDS. How robust are Algorithms 1 and 2 in settings with noise? Could they be applied directly to real-world datasets while still exhibiting long-range memorization?\n\n2) What is the intended takeaway from Section 4.2, and do you think it would benefit from benchmarking against other models?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "louF53dmqg", "reviewer": "Reviewer_usFi", "summary": "The paper introduces a novel theoretical framework addressing length generalization in sequence prediction tasks using spectral filtering methods. It defines a new metric, Asymmetric-Regret, that quantifies the regret of predictors trained with shorter contexts against those trained with longer ones. The authors provide rigorous proofs demonstrating that spectral filtering predictors can achieve provable length generalization under certain conditions on the linear dynamical system (LDS). A gradient-based learning algorithm is proposed that provably achieves length generalization for linear dynamical systems. Experimental validations on synthetic datasets confirm theoretical predictions.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for a thoughtful and detailed review!\n\nQ1 (Realistic Systems)\n\n This is a good question. On the face of it - linear dynamical systems are a toy mathematical model, and it is unclear if real dynamics are linear or symmetric. However: 1) our bounds do not depend on the hidden dimension, so one can imagine very complex dynamics that we only see their projection. 2) Some previous papers such as [2,3,4], argue that LDS have good modeling capacity for language, even with symmetric transition matrices. 3) Our work extends to very recent advances in spectral filtering by [5], such that it extends to more general linear dynamical systems. \n\nQ2 (Induction Heads Task)\n\nThis is only for simplifying the setting, there is no need for this assumption, and we could have experimented with random extensions just as well.\n\nQ3 (Figure 5)\n\nThis is just a notation, you are 100\\% correct that above 1 has no meaning, but the standard mathematical notation is mean+std, which can be larger than 1, so we went with that. Our preference would be to cut off at 1.  Missing footnote 3 said \"Even though the accuracy cannot go above $1$, the error bars are still well defined above this value.\" We will make sure this compiles correctly.\n\n\nReferences\n\n\n[2] Resurrecting Recurrent Neural Networks for Long Sequences\nAntonio Orvieto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, Soham De \n\n[3] Efficiently modeling long sequences with structured state spaces\nA Gu, K Goel, C Ré\n\n[4] Spectral state space models\nN Agarwal, D Suo, X Chen, E Hazan\n\n[5] Dimension-free Regret for Learning Asymmetric Linear Dynamical Systems\nAnnie Marsden, Elad Hazan", "claims_and_evidence": "The paper makes clear theoretical claims supported by rigorous proofs. However, experimental evidence is limited to synthetic data, focusing on linear dynamical systems. Broader applicability to nonlinear or noisy settings is not fully explored.", "methods_and_evaluation_criteria": "The proposed spectral filtering methods are theoretically well-justified and the evaluation via Asymmetric-Regret is suitable for the studied context.", "theoretical_claims": "The correctness of the theoretical proofs (Theorems 1, 2, 4, 5, 6) appears solid within the assumptions stated.", "experimental_designs_or_analyses": "The synthetic experiments are well-designed to validate theoretical predictions. They clearly demonstrate the conditions under which length generalization occurs.", "relation_to_broader_scientific_literature": "This paper clearly follows a series of works by Hazan et al. (2016, 2017a, 2017b, 2018, 2020). The introduction of Asymmetric-Regret and the theoretical guarantees provided for spectral filtering represent a meaningful extension of this line of work.", "essential_references_not_discussed": "Not to my knowledge", "other_strengths_and_weaknesses": "### Strengths\n1. Clearly articulated and rigorous theoretical analysis.\n2. Introduction of the insightful Asymmetric-Regret metric.\n\n### Weaknesses\n1. The notion and details of Spectral Transform Unit (STU) need further clarification and motivation.", "other_comments_or_suggestions": "1. Incorporate bibliography into the main manuscript rather than supplementary material.\n2. Minor: Use standard notation for real numbers (\\mathbb{R} instead of \\mathcal{R}).\n3. Minor: Juxtapose Algorithms 1 and 2 for easier comparative readability.", "questions_for_authors": "1. Could you provide examples of realistic systems where the spectral assumptions are met?\n\n2. In Induction Heads Task, why assume the rest of the sequence consists of the same special blank token? Is this simplification necessary for theoretical clarity or could it be relaxed?\n\n3. In Figure 5, why does the upper boundary of confidence intervals exceed accuracy = 1? Clarify missing footnote 3.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "43epaL5ri5", "reviewer": "Reviewer_Cycx", "summary": "- This paper considers the problem of length generalization for sequence prediction in linear dynamic systems. \n- They define a new notion of regret, called Asymmetric Regret, which measures the difference in cumulative loss between an algorithm that is only allowed to use information in the past $L$ time points and the cumulative loss of a policy that is allowed to use information in the past $L'$ time points, where $L' \\geq L$. \n- The authors provide two spectral-filtering based algorithms, based on what assumptions one places on the LDS, that obtain sub-linear asymmetric regret when one takes $L' = T$ and $L = T^q$ for $q \\in [0, 1]$.  The first algorithm obtains sublinear regret for any $q \\in [0, 1]$, as long as the LDS satisfies certain constraints on its eigenvalues. The second algorithm removes the assumption needed on the LDS, but requires that $q \\geq \\frac{1}{4}$. \n- Finally, the authors corroborate their theoretical findings with experiments.\n\n## Update after rebuttal\nI thank the authors for their response. As they have addressed most of my questions and concerns, I will maintain my positive score for this paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and detailed review!\n\nConnection to LLMs Response\n\nYou are correct - we have zero theory for LLMs, and unfortunately this is not uncommon, our theoretical understanding of LLM is very limited. We see this as a start of a theory for length generalization for *any* sequence, and the easiest sequence we could start with is that for linear dynamical systems. It is rich enough to have been used in LLM applications, please see papers [2,3,4], and yet amenable to analysis. In section 4.2 we show that despite our analysis only holds for the basic mathematical model of linear dynamical systems, our techniques actually do apply for more sophisticated signals, showing evidence that the theory can be enhanced in the future to incorporate the language signal.  \n\n\n\nEmpirical Validation Response\n\nOur experiments are proof-of-concept, and are not immediately applicable to LLMs, although we certainly hope they will in the future. We assume you mean comparing the performance of Algorithm 1 and 2 (not 5 and 6?). In fact, we do compare them on page 7, showing that Algorithm 2 is much more robust to the spectrum of $A$. That's a great suggestion to include plots for $L = T^{1/4}$ and smaller in Figure 4. We will do this. \n\n\n\n[2] Resurrecting Recurrent Neural Networks for Long Sequences\nAntonio Orvieto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, Soham De \n\n[3] Efficiently modeling long sequences with structured state spaces\nA Gu, K Goel, C Ré\n\n[4] Spectral state space models\nN Agarwal, D Suo, X Chen, E Hazan", "claims_and_evidence": "Yes, the claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the proposed evaluation criteria, namely Asymmetric regret, makes sense for the problem at hand.", "theoretical_claims": "I did not check the correctness of the proofs of the Theorem statements.", "experimental_designs_or_analyses": "Yes, I reviewed the experiments in Section 4, namely the experiments in Section 4.1.", "relation_to_broader_scientific_literature": "Length generalization, the ability for learning algorithms trained using one context window size to generalize to much longer context windows, has even extensively studied empirically in the context of large language models. This paper initiates the theoretical study of length generalization in the context of learning linear dynamic systems. To the best of my knowledge, this is the first paper to formalize this problem in the context of linear dynamical systems.", "essential_references_not_discussed": "No, I believe that the authors adequately summarized existing related works.", "other_strengths_and_weaknesses": "**Strengths**: \n- The paper is well-written and easy to follow\n- I found the notion of Asymmetric regret to be interesting and this work to be timely due to the recent interest in length generalization for LMs\n\n**Weaknesses**:\n-  The connection to LLMs is unclear. In lines 40 - 44, the authors make it a point to emphasize the difficulty of length generalization in the context of LLMs. However, to me, it's unclear how studying length generalization for LDS has any bearing to length generalization for LLMs. It would be great if the authors can discuss, at a high-level, what implications the main take aways from this paper have on length generalization in LLMs. I think this is important, because it's not clear to me why one should care about length generalization for LDS (i.e why would I run Algorithms 5 and 6 when learning LDS?)\n\n- Limited Empirical Evaluation. The authors effectively only run a single experiment. It would be nice to see the empirical performance of Algorithms 5 and 6 across a larger set of experiments, perhaps using real-world data. Moreover, the authors provide two algorithms, but don't provide an empirical comparison between them. I would be interested in seeing how the performance of Algorithm 5 and 6 compare, and whether the requirement that $q \\geq \\frac{1}{4}$ for Algorithm 6 is really needed in practice.", "other_comments_or_suggestions": "- Typo in equation (1)? Should is be $y_{t} = C x_t + D u_t + \\zeta_t$? Likewise, in the equation in the right hand side column around likes 41, shouldn't $u_t$ be used when making a prediction about $\\hat{y}_t$?", "questions_for_authors": "See weaknesses above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers are in consensus that this is a strong contribution to ICML.  

They should implement the following before publication:
_(i) provide a deeper discussion of length generalization in this work and the related literature, (BkYk)_ 
_(ii) highlight the notion of regret and the case, as described in their rebuttal. (BkYk)_
They have also made promises to implement a round of changes in their own comments, which this AC encourages them to follow through on.
Decision: Accept (poster)