Provable Length Generalization in Sequence Prediction via Spectral Filtering

## Abstract

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 filtering algorithm. We present a gradient-based learning algorithm that provably achieves length generalization for linear dynamical systems. We conclude with proof-of-concept experiments which are consistent with our theory.

## 1 Introduction

Sequence prediction is a fundamental problem in machine learning with widespread applications in natural language processing, time-series forecasting, and control systems. In this setting, a learner observes a sequence of tokens and iteratively predicts the next token, suffering a loss that measures the discrepancy between the predicted and the true token. Predicting future elements of a sequence based on historical data is crucial for tasks ranging from language modeling to autonomous control.

A key challenge in sequence prediction is understanding the role of context length—the number of previous tokens used to make the upcoming prediction—and designing predictors that perform well with limited context due to computational and memory constraints. These resource constraints become particularly significant during the training phase of a predictor, where the computational cost of using long sequences can be prohibitive. Consequently, it is beneficial to design predictors that can learn from a smaller context length while still generalizing well to longer sequences. This leads us to the central question of our investigation: Can we develop algorithms that learn effectively using short contexts but perform comparably to models that use longer contexts?

To address this question, we introduce a new performance metric—Asymmetric-Regret—which measures the difference in total prediction loss between an online predictor with limited context length and a benchmark predictor with a longer context. Unlike classical regret, which assumes both the learner and the benchmark operate under the same conditions, Asymmetric-Regret accounts for the asymmetry in context lengths, providing a more realistic assessment of performance in resource-constrained settings. With a formal and well-defined notion of Asymmetric-Regret in hand, we begin our investigation with the following question: are there algorithms that can attain non-trivial bounds on the Asymmetric-Regret for natural sequences?

We explore this concept through the lens of spectral filtering algorithms (Hazan et al., , ). Spectral filtering has emerged as a robust method for learning linear dynamical systems when the system is unknown and the hidden state is unobserved. Beyond their theoretically sound properties, spectral filtering-based predictors have proven practical in recent applications. Notably, the Spectral Transform Unit (Agarwal et al., ), a neural architecture built using spectral filtering, has recently shown promise on sequence prediction over a range of modalities (Liu et al., ).

In this work, we extend the theoretical understanding of spectral filtering by demonstrating that these predictors can achieve length generalization. Specifically, we present a gradient-based online learning algorithm for spectral filtering and show that we can train on a smaller context length while still achieving the same regret bounds as if we had trained on a longer context length. Formally, we prove that this algorithm guarantees sublinear Asymmetric-Regret, indicating that the performance gap diminishes as the sequence length increases.

Beyond theoretical interest, our work is practically motivated by challenges in length generalization faced by large language models (LLMs). Current LLMs often struggle to generalize to longer sequences than those seen during training (Abbe et al., ; Anil et al., ; Jelassi et al., ; Zhou et al., ; Delétang et al., ; Dziri et al., ; Zhou et al., ) and a significant body of empirical research has been dedicated to addressing this limitation (Kazemnejad et al., ; Shen et al., ; Dai, ; Chi et al., ; Li et al., ; Press et al., ). Despite its importance and extensive empirical research, provable theoretical results on length generalization remain largely elusive. We view our work as a step toward addressing this gap. More practically, most methods introduced to improve length generalization are task-specific. Our work suggests that neural architectures that incorporate spectral filtering, like the Spectral Transform Unit, have the potential to provide robust length generalization.

### 1.1 Our Contributions

Consider online sequence prediction in which the predictor iteratively receives input $u_{t}\in{\mathcal{R}}^{d_{\textrm{in}}}$ and then makes a prediction $\hat{y}_{t}\in{\mathcal{R}}^{d_{\textrm{out}}}$ of the output, after which the true output $y_{t}$ is revealed. The goal of the predictor is to minimize error according to a given convex and Lipschitz loss function $\ell_{t}(y_{t},\hat{y}_{t})$. In this work we consider the class of *spectral filtering* predictors, introduced by Hazan et al. (). A spectral filtering predictor is characterized by parameters $(T,{M_{i}}_{i=1}^{k},k)$ and outputs predictions $\hat{y}_{t}$ of the form

$$ $\hat{y}_{t}=y_{t-1}+\sum_{i=1}^{k}M_{i}u_{(t-1):0}\phi_{i},$ $$

where $u_{(t-1):0}\in\mathbb{R}^{d_{\textrm{in}}\times T}$ is a matrix whose columns are the previous inputs $u_{t-1},u_{t-2},\dots,u_{0}$ (possibly zero-padded as necessary), $\{\phi_{j}\}_{j=1}^{k}$ are the $T$-dimensional spectral filters, $\left\{M_{i}\right\}_{i=1}^{k}\subset{\mathcal{R}}^{d_{\textrm{out}}\times d_{
\textrm{in}}}$ are matrices which are learned online, and $k$ is the number of filters used. Hazan et al. () provide an algorithm to learn $\left\{M_{i}\right\}_{i=1}^{k}$ and show this achieves nearly optimal regret bounds when measured against the best Linear Dynamical System (LDS) predictor. We investigate whether it is necessary to use the entire history $u_{(t-1):0}$ to learn the optimal set of matrices $\left\{M_{i}\right\}_{i=1}^{k}$. More broadly, we explore whether predictor classes and corresponding online learning algorithms exist that can achieve context length generalization—that is, they use only a 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 is poor regardless of the context length used. Therefore, it is important to note that one of the key features of spectral filtering predictors is that they are able to perform well on systems that have long memory (Hazan et al., ).

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 $L^{\prime}$ against the best predictor which is allowed to use (potentially much longer and therefore asymmetric) context length $L$. Let $\prod_{L}$ denote the class of predictors in $\prod$ which use context length $L$. Given an algorithm ${\mathcal{A}}(L^{\prime})$ which learns over predictors from some class $\prod_{L^{\prime}}$, the Asymmetric-Regret over horizon $T$ is

$$ $\mathrm{Regret}_{\mathrm{Asymmetric},T}\left({\mathcal{A}}(L^{\prime}),\prod_{ L}\right)\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{t=1}^{T}\ell_{t}(y_{t}, \hat{y}_{t}^{{\mathcal{A}}(L^{\prime})})-\min_{\pi\in\prod_{L}}\ell_{t}(y_{t}, \hat{y}_{t}^{\pi}).$ $$

Our main result shows that spectral filtering generalizes from a history of $T^{q}$, where $q\in[0,1]$, to $T$ for certain linear dynamical systems. It is formally given in the following theorem.

###### Theorem 1 .

Let $T\in\mathbb{Z}_{~{}\geq~{}0}$ and $q\in[0,1]$. Consider a sequence $(y_{1},\dots,y_{T})$ generated by an unknown and noiseless linear dynamical system defined by matrices $(A,B,C,D)$ as per Eq. 1. Assume the input sequence $u_{0:(t-1)}$ is sufficiently well-conditioned, satisfying $\sum_{t=0}^{T-1}(T-t)u_{t}u_{t}^{\top}\succeq\left(\frac{2|C||B|}{\sqrt{T}}
\right)I$. Suppose the eigenvalues of $A$ lie within the range $\left[0,1-\frac{\log(T)}{8T^{q}}\right]\cup\left[1-\frac{1}{2T^{5/4}},1\right]$.

Let $\mathcal{A}(L)$ denote Algorithm 1 operating with context length $L$, and let $\prod^{\mathrm{SF}}_{L}$ denote the class of spectral filtering predictors using context length $L$. For the squared loss $\ell_{t}(y,y^{\prime})=|y-y^{\prime}|^{2}$ and sufficiently large $T$, it holds that:

$$ $\mathrm{Regret}_{\mathrm{Asymmetric},T}\left({\mathcal{A}}(T^{q}),\prod^{ \mathrm{SF}}_{T}\right)~{}\leq~{}\tilde{O}(\sqrt{T}).$ $$

This theorem indicates that for any $q\in[0,1]$, the Asymmetric-Regret is bounded by $\tilde{O}(\sqrt{T})$. However, as $q$ decreases, the class of linear dynamical systems for which this bound holds becomes more restricted due to the eigenvalue 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-stable and standard predictors which aim to use low memory typically fail. Critically, Theorem 1 holds even for these marginally-stable systems. When interpreting this result, it’s important to note that the class of spectral filtering predictors $\prod^{\mathrm{SF}}_{T}$ which use the full context length are provably able to predict well on marginally-stable Linear Dynamical Systems (Hazan et al., )(^1^11The only LDS’s for which there can be any useful results are those with $A$’s eigenvalues in $[-1,1]$, i.e. marginally-stable systems. We recall that the spectral filtering principle can be readily applied to handle negative eigenvalues in $[-1,0]$ (see Appendix D of Agarwal et al. (), for example). For ease of presentation, we focus on capturing the length generalization effects of eigenvalues in $[0,1]$ in the sequel, and so we suppose without loss of generality that $A\succeq 0$.). Therefore, this result implies that spectral filtering predictors are able to context length generalize in a nontrivial way.

Inspired by particular spectrum of $A$ that is required for the classical Spectral Filtering algorithm to achieve length generalization, we develop a novel variation on the Spectral Filtering algorithm, presented in Algorithm 2, which achieves length generalization without added assumptions on the spectrum of $A$ (whenever the context-length is at least $T^{1/3}$). Algorithm 2 achieves this by using two autoregressive components $y_{t-1}$ and $y_{t-2}$ to construct its prediction $\hat{y}_{t}$ of $y_{t}$. We provide the following theoretical result.

###### Theorem 2 .

Let $T\in\mathbb{Z}_{~{}\geq~{}0}$ and $q\in[0,1]$. Consider a sequence $(y_{1},\dots,y_{T})$ generated by an unknown and noiseless linear dynamical system defined by matrices $(A,B,C,D)$ as per Eq. 1. Assume the input sequence $u_{0:(t-1)}$ is sufficiently well-conditioned, satisfying $\sum_{t=0}^{T-1}(T-t)u_{t}u_{t}^{\top}\succeq\left(\frac{2|C||B|}{\sqrt{T}}
\right)I$. Suppose the eigenvalues of $A$ lie within the range $\left[0,1-\frac{\log(T)}{8T^{q}}\right]\cup\left[1-\frac{1}{2T^{1/4}},1\right]$.

Let $\mathcal{A}(L)$ denote Algorithm 2 operating with context length $L$, and let $\prod^{\mathrm{SF}}_{L}$ denote the class of spectral filtering predictors using context length $L$. For the squared loss $\ell_{t}(y,y^{\prime})=|y-y^{\prime}|^{2}$ and sufficiently large $T$, it holds that:

$$ $\mathrm{Regret}_{\mathrm{Asymmetric},T}\left({\mathcal{A}}(T^{q}),\prod^{ \mathrm{SF}}_{T}\right)~{}\leq~{}\tilde{O}(\sqrt{T}).$ $$

Observe that if $q~{}\geq~{}1/3$, then $[0,1-\log(T)/(8T^{q})]\cup[1-1/T^{1/4},1]=[0,1]$ for any $T>0$ and so we do not constrain the spectrum of $A$ to get length generalization (aside from assuming it has nonnegative eigenvalues).

Our next contribution is the development of a new class of predictors we call tensorized spectral filters. Tensorized spectral filters possess more structure than their original counterparts and are provably more expressive—they can learn a select class of time-varying linear dynamical systems that vanilla spectral filtering cannot. We develop a novel context-length dependent algorithm for tensorized spectral filtering which, similar to Algorithm 2, requires two autoregressive components.

###### Theorem 3 .

Let $T\in\mathbb{Z}_{~{}\geq~{}0}$ and $q\in[0,1]$. Consider a sequence $(y_{1},\dots,y_{T})$ generated by an unknown and noiseless linear dynamical system defined by matrices $(A,B,C,D)$ as per Eq. 1. Assume the input sequence $u_{0:(t-1)}$ is sufficiently well-conditioned, satisfying $\sum_{t=0}^{T-1}(T-t)u_{t}u_{t}^{\top}\succeq\left(\frac{2|C||B|}{\sqrt{T}}
\right)I$. Suppose the eigenvalues of $A$ lie within the range $\left[0,1-\frac{\log(T)}{8T^{q}}\right]\cup\left[1-\frac{1}{2T^{1/4}},1\right]$.
Let $\mathcal{A}(L)$ denote Algorithm 3 operating with context length $L$, and let $\prod^{\mathrm{SF}}_{L}$ denote the class of spectral filtering predictors using context length $L$. For the squared loss $\ell_{t}(y,y^{\prime})=|y-y^{\prime}|^{2}$ and sufficiently large $T$, it holds that:

$$ $\mathrm{Regret}_{\mathrm{Asymmetric},T}\left({\mathcal{A}}(T^{q}),\prod^{ \mathrm{SF}}_{T}\right)~{}\leq~{}\tilde{O}(\sqrt{T}).$ $$

Finally, we experimentally confirm the results of Theorem 1 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 an LDS which has eigenvalues in the “bad” range $[1-\log(T)/(8T^{q}),1-1/(2T^{5/4})]$ we find that the limited context length spectral filtering predictors are unable to length generalize. However, when the data is generated by and LDS which has eigenvalues “hugging” this bad range (i.e. either just smaller than $1-\log(T)/(8T^{q})$ or just larger than $1-1/(2T^{5/4})$), the limited context length spectral filtering predictors successfully length generalize. Next, 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 generalization. This suggests that incorporating spectral filtering into neural architectures, like the STU, may provide improved length generalization in deep learning applications. We leave further empirical study on this for future work.

###### Theorem 1 .

###### Theorem 2 .

###### Theorem 3 .

### 1.2 Related Work

The literature for sequence prediction is too broad to survey in detail, so we give a few highlights of the recent rapid advancements. The most notable progress includes the Transformer model (Vaswani et al., ) that incorporates an attention mechanism for accurate sequence prediction in many domains (Brown et al., ; Dosovitskiy et al., ; Jumper et al., ). Transformer models and their attention layers have memory/computation requirements that scale quadratically with context length. Many approximations have been proposed (see Tay et al. () for a recent survey).

Motivated by the high memory and compute requirements of transformers, state space models were revisited starting from (Gu et al., , ) who propose and develop the HiPPO theory. Gu et al. () develop the S4 parameterization to address the bottlenecks of training efficiency, performance and numerical stability. Further works in the area show SOTA performance and include Gupta et al. (); Smith et al. (); Orvieto et al. (); Gu & Dao ().

State space models are very efficient for training and inference, but can suffer in long-context applications. This motivated the use of spectral filtering technique for learning marginally-stable linear dynamical systems (Hazan et al., , ). This technique was incorporated to a neural architecture in Agarwal et al. (), that was recently shown to perform well across several modalities (Liu et al., ).

From an applied perspective, generalization in sequence prediction has been recently studied in Hou et al. () through the theoretical lens of Turing programs. They propose a methodology that empirically improves length generalization across a diverse set of tasks. There are also architecture-specific approaches to length generalization such as ALiBi positional embeddings for transformers (Press et al., ), but such methods lack provable guarantees and can have varying empirical performance (Kazemnejad et al., ).

In contrast, our investigation starts from the theory of regret minimization in games and online learning. Regret minimization has the advantage that it implies generalization in the statistical learning setting (see e.g. Cesa-Bianchi et al. ()) and is usually accompanied by efficient algorithms such as online gradient descent (see e.g. Hazan et al. ()). Our new notion of Asymmetric-Regret incorporates asymmetric information access between the online learner and the benchmark class.

## 2 Background and Setting

In the online sequence prediction setting the predictor iteratively receives input $u_{t}$ and makes prediction $\hat{y}_{t}$ of the output, after which the true output $y_{t}$ is revealed. The goal is to minimize error according to a given (convex Lipschitz) loss function $\ell_{t}(y_{t},\hat{y}_{t})$.

In online learning, we usually do not make statistical assumptions about the generation of the input sequence. As such, performance is measured relative to a certain benchmark class of predictors. For example, a linear predictor predicts according to the rule

$$ $\pi_{M_{1:k},N_{1:l}}(u_{0:(t-1)},y_{1:t-1})=\sum_{i=1}^{k}M_{i}u_{t-i}+\sum_{ j=1}^{l}N_{j}y_{t-j}.$ $$

A prediction algorithm ${\mathcal{A}}$ is measured by regret, or difference in total loss, vs. a class of predictors $\prod$ (such as linear predictors), i.e.

$$ $\mbox{{Regret}}_{T}({\mathcal{A}},\prod)=\sum_{t=1}^{T}\ell_{t}(y_{t},\hat{y}_ {t}^{\mathcal{A}})-\min_{\pi\in\prod}\sum_{t=1}^{T}\ell_{t}(y_{t},\hat{y}_{t}^ {\pi}).$ $$

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

$$ $x_{t+1}=Ax_{t}+Bu_{t}+w_{t}\ \ ,\ \ y_{t+1}=Cx_{t}+Du_{t}+\zeta_{t},$ (1) $$

where $x_{t}$ is the (hidden) state, $u_{t}$ is the input or control to the system, and $y_{t}$ is the observation. The terms $w_{t},\zeta_{t}$ are noise terms, and the matrices $A,B,C,D$ are called the system matrices.
A linear dynamical predictor with parameters $A,B,C,D$ predicts according to

$$ $\pi_{ABCD}(u_{0:(t-1)},y_{1:t-1})=\hat{y}_{t}^{\pi}=\sum_{i=1}^{t}CA^{i}Bu_{t- i}+Du_{t}.$ $$

The best such predictor for a given sequence is also called the optimal open loop predictor, and it is accurate if the signal is generated by a LDS without noise.

### 2.1 Context Length Generalization and the Asymmetric-Regret metric

We say that an online predictor has context length $L$ if it bases its prediction $\hat{y}_{t}$ only on information from the previous $L$ timesteps, i.e. $u_{t:t-L}$ and $y_{t:t-L}$. Open loop predictors base their prediction only on $u_{t:t-L}$, whereas closed loop predictors can also use $y_{t:t-L}$.

For example, the class of all linear open loop predictors with context lengths $L$ is given by

$$ $\prod_{L}^{OL}=\left\{\pi_{M_{1:L}}\;|\;\pi_{M_{1:L}}(u_{(t-1):0})=\sum_{i=1}^ {L}M_{i}u_{t-i}\right\}.$ $$

The key question in our work is whether there are predictor classes with corresponding online learning algorithms which context length generalize in the sense that they learn the best predictor in the class using a short context length, but they perform well compared to the best predictor which is allowed to use long context length. To formalize this notion, we introduce Asymmetric-Regret whose definition we restate here:

###### Definition 4 (Asymmetric-Regret) .

Let $\prod_{L^{\prime}}^{\textrm{learn}}$ be a class of predictors which use context length $L^{\prime}$ and let $\prod_{L}^{\textrm{ref}}$ be a reference class of predictors which use context length $L$. The *Asymmetric-Regret* with respect to (convex Lipschitz) loss $\ell_{t}$ over horizon $T$ of an algorithm ${\mathcal{A}}(L^{\prime})$ which tries to learn a predictor from $\prod_{L^{\prime}}^{\textrm{learn}}$ is

$$ $\mathrm{Regret}_{\mathrm{Asymmetric},T}\left(\mathcal{A}(L^{\prime}),\prod_{L} ^{\textrm{ref}}\right)\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{t=1}^{T} \ell_{t}(y_{t},\hat{y}_{t}^{{\mathcal{A}}(L^{\prime})})-\min_{\pi\in\prod_{L}} \sum_{t=1}^{T}\ell_{t}(y_{t},\hat{y}_{t}^{\pi}).$ $$

###### Definition 4 (Asymmetric-Regret) .

### 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., ). The idea is to project the sequence of inputs to a small subspace that is constructed using the special structure of discrete linear dynamical systems. The output of the spectral filtering predictor is represented as

$$ $\hat{y}_{t}=y_{t-1}+\sum_{i=1}^{k}M_{i}{u}_{(t-1):0}\phi_{i},$ (2) $$

where $u_{(t-1):0}\in\mathbb{R}^{d_{\textrm{in}}\times T}$ is a matrix whose columns are the previous inputs $u_{t-1},\dots,u_{0}$ (possibly zero-padded as necessary), $\{\phi_{j}\}_{j=1}^{k}$ are the $T$-dimensional spectral filters that can be computed offline given the target sequence length $T$, and $\left\{M_{i}\right\}_{i=1}^{k}\subset{\mathcal{R}}^{d_{\textrm{out}}\times d_{
\textrm{in}}}$ 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.

Let $\mu_{\alpha,T}=(1-\alpha)[1,\alpha,\alpha^{2},...,\alpha^{T}]$ be the (weighted) impulse-response vector corresponding to a one dimensional linear dynamical system with parameter $\alpha$ unfolded to $T$ time steps, and consider the symmetric matrix

$$ $H_{T}\stackrel{{\scriptstyle\text{def}}}{{=}}\int_{0}^{1}\mu_{\alpha,T}\mu_{ \alpha,T}^{\top}d\alpha.$ (3) $$

Since $H_{T}$ is a real PSD matrix, it admits a real spectral decomposition, and the (non-negative) eigenvalues can be ordered naturally by their value. Let
$\{(\sigma_{j}\in\mathbb{R},\phi_{j}\in\mathbb{R}^{L})\}_{j=1}^{L}$ be the eigenvalue-eigenvector pairs of $H_{T}$ ordered to satisfy $\sigma_{1}~{}\geq~{}\sigma_{2}~{}\geq~{}\ldots~{}\geq~{}\sigma_{d}$. The spectral filters $\phi_{1},...,\phi_{k}$ are exactly those first $k$ eigenvectors corresponding to the largest eigenvalues.
The spectral filtering class is further parameterized by matrices $M_{1},...,M_{k}\in\mathbb{R}^{d_{\text{out}}\times d_{\text{in}}}$. The output at time $t$ is then given by equation (2).

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 5 (Simplified from Hazan et al. ( 2017a ) ) .

Given any linear dynamical system parametrized by $A,B,C,D$ such that $A$ is a PSD matrix with $\|A\|~{}\leq~{}1$, there exists matrices $M_{1},...,M_{K}$, such that for all $L$ and all sequences $u_{1:L},\|u_{t}\|~{}\leq~{}1$, the following holds. Let $y^{\mathrm{LDS}}_{1:L}$ be the sequence generated by execution of the LDS via (1) and $y^{\mathrm{SF}}_{1:L}$ be the sequence generated by Spectral Filtering via (2). Then for all $t\in[L]$,

$$ $\|y^{\mathrm{LDS}}_{t}-y^{\mathrm{SF}}_{t}\|\sim e^{-\frac{k}{\log(L)}}.$ $$

Theorem 5 establishes that Spectral Filtering can predict long memory sequences since the statements holds even over marginally stable linear dynamical systems.

###### Theorem 5 (Simplified from Hazan et al. ( 2017a ) ) .

## 3 Learning with a Short Context—Provable Length Generalization for Linear Dynamical Systems

In Algorithm 1, we modify the classical online learning algorithm for spectral filtering to use a shorter context window. 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$:

$$ $\ell_{t}(M,L)\stackrel{{\scriptstyle\text{def}}}{{=}}\|y_{t}-y_{t-1}-\sum_{i=1 }^{k}M_{i}u_{(t-1):(t-L)}\phi_{i}\|^{2},$ $$

where $\left\{M_{i}\right\}_{i=1}^{k}$ and $\left\{\phi_{i}\right\}_{i=1}^{k}$ are as defined for Eq. 2 and $u_{(t-1):(t-L)}\in\mathbb{R}^{d_{\textrm{in}}\times T}$ is the matrix $u_{(t-1):0}$ but with the columns corresponding to the inputs after context length $L$, i.e. $u_{t-L-1},\dots,u_{0}$, zeroed out.
Note that this is overloaded notation compared with $\ell_{t}(y,y^{\prime})$ which measures the loss of the true $y$ with the predicted $y^{\prime}$ as used in our definition of regret. The context length specific loss can be written equivalently as

$$ $\ell_{t}(M,L)=\|\hat{y}(M^{t},L)-y_{t}\|^{2},$ $$

where $\hat{y}(M^{t},L)$ denotes the prediction of $y_{t}$ using iterate $M^{t}$ and context window size $L$ as in Eq. 4 of Algorithm 1.

Figure: Algorithm 1 Spectral Filtering with Limited Context

To provide a precise statement on length generalization, we present the following performance guarantee. Note that we measure loss differently for our prediction and the benchmark predictor—the comparator has access to more information. Therefore, this guarantee is stronger and more challenging to obtain than classical regret bounds. Note that we prove the following for a noiseless $(A,B,C,I)$-LDS rather than $(A,B,C,D)$ which is without loss of generality since we can consider the input as $Du_{1},\dots,Du_{T}$.

###### Theorem 6 .

Let $T\in\mathbb{Z}_{~{}\geq~{}0}$ and $q\in[0,1]$. Consider a sequence $(y_{1},\dots,y_{T})$ generated by an unknown and noiseless linear dynamical system defined by matrices $(A,B,C,I)$ as per Eq. 1. Assume the input sequence $u_{0:(t-1)}$ is sufficiently well-conditioned, satisfying $\sum_{t=0}^{T-1}(T-t)u_{t}u_{t}^{\top}\succeq\left(\frac{2|C||B|}{\sqrt{T}}
\right)I$. Suppose the eigenvalues of $A$ lie within the range $\left[0,1-\frac{\log(T)}{8T^{q}}\right]\cup\left[1-\frac{1}{2T^{5/4}},1\right]$. Let $k=\Omega\left(\log(T)\cdot\log\left(Td_{A}\right)\right)$, $r~{}\geq~{}\|B\|\|C\|$, and assume $T~{}\geq~{}(4k\log(T)/\|C\|\|B\|)^{4}$. Algorithm 1 satisfies:

$$ $\mathrm{Regret}_{\mathrm{Asymmetric},T}\left({\mathcal{A}}(T^{q}),\prod^{ \mathrm{SF}}_{T}\right)=\sum_{t=1}^{T}\ell_{t}(M^{t},T^{q})-\min_{M^{*}\in \mathcal{K}_{r}}\sum_{t=1}^{T}\ell_{t}(M^{*},T)~{}\leq~{}O\left(\|B\|^{2}\|C\| ^{2}k^{3/2}\log(T)\sqrt{T}\right).$ $$

The proof of Theorem 6 is in Appendix B with a high-level overview in Section 3.1. This theorem shows that the sequence $M^{1},\dots,M^{T}$ constructed by Algorithm 1, even when using a reduced context length of size $T^{q}$, is able to achieve regret $O(\sqrt{T})$ when compared to the best spectral filter that uses full context length $T$.

To better understand the eigenvalue ranges not covered by Theorem 6, Figure 1 highlights the regions of $[0,1]$ that are excluded from the theorem’s guarantee for different context lengths $T^{q}$. The $x$-axis represents $T$ on the x-axis and the unfavorable subsets of $[0,1]$ are depicted as vertical slices. As $T$ and $q$ increase, our coverage of $[0,1]$ improves.
Notably, our method applies even to marginally stable systems that exhibit long memory due to eigenvalues $\alpha\in[1-1/(2T^{5/4}),1]$.

Figure: Figure 1: Regions of $[0,1]$ not covered by Theorem 6, with $T$ on the x-axis. For convenience, in the right image we zoom in to $[0.999,1]$.
Refer to caption: extracted/5972412/figs/combined_eigvalintervals.png

Motivated by the limitations of Theorem 6 to provide a length generalization that is robust to the spectrum of $A$, we introduce a variation on the classical Spectral Filtering algorithm, presented as Algorithm 2. This algorithm uses the two most previous outputs $y_{t-1}$ and $y_{t-2}$ when making prediction $\hat{y}_{t}$ of $y_{t}$.

This algorithm has a slightly different construction of spectral filters. Indeed, they are the eigenvectors of the following matrix

$$ $N_{T}\stackrel{{\scriptstyle\text{def}}}{{=}}\int_{0}^{1}\tilde{\mu}_{\alpha,T }\tilde{\mu}_{\alpha,T}^{\top}d\alpha,$ (5) $$

where $\tilde{\mu}_{\alpha,T}\stackrel{{\scriptstyle\text{def}}}{{=}}(1-\alpha)^{2}[1
,\alpha,\alpha^{2},\dots,\alpha^{T}]$. Interestingly, 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 $T^{1/3}$ then no extra assumptions on the spectrum of $A$ are necessary to achieve our notion of length generalization. We state this formally in the following theorem.

Figure: Algorithm 2 Spectral Filtering with Limited Context and Two Autogressive Components

###### Theorem 7 .

Let $T\in\mathbb{Z}_{~{}\geq~{}0}$ and $q\in[0,1]$. Consider a sequence $(y_{1},\dots,y_{T})$ generated by an unknown and noiseless linear dynamical system defined by matrices $(A,B,C,I)$ as per Eq. 1. Assume the input sequence $u_{0:(t-1)}$ is sufficiently well-conditioned, satisfying $\sum_{t=0}^{T-1}(T-t)u_{t}u_{t}^{\top}\succeq\left(\frac{2|C||B|}{\sqrt{T}}
\right)I$. Suppose the eigenvalues of $A$ lie within the range $\left[0,1-\frac{\log(T)}{8T^{q}}\right]\cup\left[1-\frac{1}{2T^{1/4}},1\right]$. Let $k=\Omega\left(\log(T)\cdot\log\left(Td_{A}\right)\right)$, $r~{}\geq~{}\|B\|\|C\|$ and assume $T~{}\geq~{}(4k\log^{2}(T)/\|C\|\|B\|)^{4}$. Algorithm 2 satisfies:

$$ $\mathrm{Regret}_{\mathrm{Asymmetric},T}\left({\mathcal{A}}(T^{q}),\prod^{ \mathrm{SF}}_{T}\right)=\sum_{t=1}^{T}\ell_{t}(M^{t},T^{q})-\min_{M^{*}\in \mathcal{K}_{r}}\sum_{t=1}^{T}\ell_{t}(M^{*},T)~{}\leq~{}O\left(\|B\|^{2}\|C\| ^{2}k^{3/2}\log^{2}(T)\sqrt{T}\right).$ $$

The proof of Theorem 7 is in Appendix C and we give a high-level overview of the proof in the following section. Observe that if $q~{}\geq~{}1/3$, then $[0,1-\log(T)/(8T^{q})]\cup[1-1/T^{1/4},1]=[0,1]$ for any $T>0$ and so we do not constrain the spectrum of $A$ to get length generalization.

###### Theorem 6 .

###### Theorem 7 .

### 3.1 High Level Proof Overview of Main Theorems

The general proof technique for both Theorem 6 and Theorem 7 is the same. First, using standard online gradient descent results we prove that the iterates $M^{t}$ achieve $O(\sqrt{T})$ regret as measured by the context-length restricted loss $\sum_{t=1}^{T}\ell_{t}(M,L)$. That is,

$$ $\sum_{t=1}^{T}\ell_{t}(M^{t},L)~{}\leq~{}\min_{M\in\mathcal{K}_{r}}\sum_{t=1}^ {T}\ell_{t}(M,L)+O(\sqrt{T}).$ (6) $$

Next we prove that the (unique) $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 $L$. That is, defining

$$ $M_{T}^{*}\stackrel{{\scriptstyle\text{def}}}{{=}}\operatorname*{arg\,min}_{M \in\mathcal{K}_{r}}\sum_{t=1}^{T}\ell_{t}(M,T),$ $$

we have

$$ $\sum_{t=1}^{T}\ell_{t}(M_{T}^{*},L)~{}\leq~{}\sum_{t=1}^{T}\ell_{t}(M_{T}^{*}, T)+O(\sqrt{T}).$ (7) $$

Since it is trivially the case that

$$ $\min_{M\in\mathcal{K}_{r}}\sum_{t=1}^{T}\ell_{t}(M,L)~{}\leq~{}\sum_{t=1}^{T} \ell_{t}(M_{T}^{*},L),$ $$

we can combine Eq. 6 and Eq. 7 to get the final notion of length generalization that

$$ $\sum_{t=1}^{T}\ell_{t}(M^{t},L)~{}\leq~{}\min_{M\in\mathcal{K}_{r}}\sum_{t=1}^ {T}\ell_{t}(M,L)+O(\sqrt{T})~{}\leq~{}\sum_{t=1}^{T}\ell_{t}(M_{T}^{*},L)+O( \sqrt{T})~{}\leq~{}\sum_{t=1}^{T}\ell_{t}(M_{T}^{*},T)+O(\sqrt{T}).$ $$

The difficult result to prove is Eq. 7. The high level idea is that when $y_{1:t}$ evolves as a noiseless LDS and when the input $u_{0:(t-1)}$ is sufficiently well-conditioned, then the minimizer for $\sum_{t=1}^{T}\ell_{t}(M,T)$ approximately recovers a 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 it would be able to achieve small loss even when restricted to a small context-length $L\ll T$. The extent to which these recovered matrices can achieve small loss when restricted to the small context-length depends on the way the algorithm chooses to predict $y_{t}$. In the case of Algorithm 1 where $y_{t}$ is predicted based only using only one autoregressive term, even having access to the true matrices is not enough to accurately predict $y_{t}$. However, in the case of Algorithm 2, having access to the true matrices as well as a second autoregressive term allows accurate prediction of $y_{t}$ even when restricted to small context-length window.

## 4 Tensorized Spectral Filtering

Adding some form of regularization to a prediction model often results in provably and empirically better generalization in many different problem settings. While length generalization differs from overall generalization, we explore how introducing regularization to spectral filters might enhance length generalization. To this end, we introduce the class of *tensorized spectral filters*.

###### Definition 8 (Tensorized Spectral Filters) .

Let $\phi_{1}^{d},\dots,\phi_{d}^{d}$ be the eigenvectors of the $d\times d$ Hankel matrix $H_{d}$ as defined in Eq. 3. The class of $(d_{1},d_{2})$-dimensional tensorized spectral filters takes the form

$$ $\left\{\phi_{i}^{d_{1}}\otimes\phi_{j}^{d_{2}}|i\in[d_{1}],j\in[d_{2}]\right\},$ $$

where $\otimes$ denotes the tensor (Kronecker) product.

Part of the motivation for considering tensorized spectral filters comes from the tensor structure of the $\mu_{\alpha,T}$ which defines the matrix $H_{T}$ in Eq. 3. Observe that for a given $\alpha$ we have,

$$ $\mu_{\alpha,L^{2}}=(1-\alpha^{L})^{-1}\cdot\mu_{\alpha,L}\otimes\mu_{\alpha^{L },L}$ $$

Therefore, up to rescaling, the set of $\mu_{\alpha,L^{2}}$ is contained in the set of tensors $\mu_{\alpha,L}\otimes\mu_{\beta,L}$:

$$ $\left\{\mu_{\alpha}^{L^{2}}|\alpha\in[0,1]\right\}\subseteq\left\{\mu_{\alpha} ^{L}\otimes\mu_{\beta}^{L}|\alpha,\beta\in[0,1]\right\}.$ (8) $$

This property ensures that we can approximate the spectral filtering algorithm with its tensor approximation as per Algorithm 3. In fact, the tensor spectral filtering algorithm is more expressive, as equation (8) hints. One can construct non-linear dynamical systems that can be approximated by tensorized spectral filters but not by spectral filtering itself. Such a system would have dynamics corresponding to the tensor

$$ $\mu_{\alpha}^{L}\otimes\mu_{\beta}^{L},$ $$

where $\beta\neq\alpha^{L}$, and thus imply changing dynamics every $L$ iterations. In the following theorem we formalize this intuition that tensorized spectral filters are just as capable at modeling linear dynamical systems.

###### Theorem 9 .

Given any linear dynamical system parametrized by $A,B,C,D$ such that $A$ is a PSD matrix with $\|A\|~{}\leq~{}1$, there exists matrices $M^{\prime},M^{\prime\prime},\{M_{ij},i,j\in[k]\}$, such that for sequences $u_{1:T}$ where $\|u_{t}\|~{}\leq~{}1$ the following holds. Let $y^{\mathrm{LDS}}_{1:T}$ be the sequence generated by execution of the LDS via (1), and $y^{\mathrm{TSF}}_{1:T}$ be the sequence generated by Tensor Spectral Filtering via:

$$ ${y}_{t}^{\mathrm{TSF}}-2{y}_{t-1}^{\mathrm{TSF}}+y_{t-2}^{\mathrm{TSF}}=M^{ \prime}u_{t}+M^{\prime\prime}u_{t-1}+\sum_{i,j=1}^{k}M_{ij}u_{t-2:1}\cdot\phi_ {i}\otimes\phi_{j}.$ $$

Then for all $t\in[T]$,

$$ $\|y^{\mathrm{LDS}}_{t}-y^{\mathrm{TSF}}_{t}\|\sim e^{-\frac{k}{\log(T)}}.$ $$

###### Definition 8 (Tensorized Spectral Filters) .

###### Theorem 9 .

### 4.1 Length Generalization with Tensorized Spectral Filtering

The representation property from Theorem 9 gives rise to a novel algorithm (Algorithm 3). Notably, this algorithm is based on online gradient descent for spectral filtering and can be shown to give the same regret bounds as the original spectral filtering algorithm from Hazan et al. ().

Figure: Algorithm 3 Tensorized Spectral Filtering

Just as in Theorem 6 and Theorem 7, we have a companion result for tensorized spectral filtering.

###### Theorem 10 .

Suppose $y_{1:t}$ evolves as a noiseless $(A,B,C,I)$-LDS where $A\in\mathbb{R}^{d_{A}\times d_{A}}$ is a PSD matrix and the input $u_{T:1}$ is such that $\sum_{t=1}^{T}(T-t)u_{t}u_{t}^{\top}\succeq(2\|C\|\|B\|/\sqrt{T})I$. Further, assume the eigenvalues of $A$ fall in the range $[0,1-\log(T)/(8T^{q})]\cup[1-1/(2T^{1/4}),1]$. Let $k=\Omega\left(\log(T)\cdot\log\left(Td_{A}\right)\right)$, $r~{}\geq~{}\|B\|\|C\|$ and assume $T~{}\geq~{}(4k\log^{2}(T)/\|C\|\|B\|)^{4}$. Algorithm 3 satisfies:

$$ $\mathrm{Regret}_{\mathrm{Asymmetric},T}=\sum_{t=1}^{T}\ell_{t}(M^{t},T^{q})- \min_{M^{*}\in\mathcal{K}_{r}}\sum_{t=1}^{T}\ell_{t}(M^{*},T)~{}\leq~{}O\left( \|B\|^{2}\|C\|^{2}k^{3}\log^{2}(T)\sqrt{T}\right).$ $$

The proof structure of Theorem 10 is the same as as the proof structure used for Theorem 6 and Theorem 7 as described in Section 3.1. The full proof of Theorem 10 is in Appendix D.

###### Theorem 10 .

## 5 Experiments

### 5.1 Linear Dynamical System

We can empirically verify Theorem 6 in an online sequence prediction task where the data is generated by a noiseless LDS. We refer to a “bad” region of eigenvalues $\left(1-{\log(T)}/({8T^{7/8}}),\;1-{1}/({2T^{5/4}})\right)$ as Region B, and we define Region A to hug Region B on both sides as shown in Figure 2.

Figure: Figure 2: The red region (Region B) represents the interval of eigenvalues for which length generalization is not guaranteed by our main theorem. The blue region (Region A) is chosen to hug Region B on both sides – to be precise, the leftmost point of Region A is $0.9\cdot\left(1-{\log(T)}/({8T^{7/8}})\right)$, and the rightmost point is $1$. This selection ensures that (1) Region $A$ will start to contain bad eigenvalues as $q$ decreases from $7/8$ and (2) eigenvalues in Region B are bad for $q~{}\leq~{}7/8$.
Refer to caption: x1.png

Theorem 6 predicts that if all the eigenvalues lie outside Region B, then spectral filtering will length generalize from $T^{7/8}$ to $T$. To confirm this, we generate a random LDS of hidden dimension 512 with half of the LDS eigenvalues uniformly sampled from each component of Region A. The online prediction losses are plotted in Figure 4 for different choices of context length $T^{q}$, where $T=2^{14}$ and $k=24$. As expected from the theory, context lengths approaching $T^{7/8}$ closely match the performance of the optimal spectral filtering predictor with full context.

Very interestingly, we see that context length $T^{1/2}$ consistently fails in a qualitatively worse fashion – indeed, some of the values in Region A are actually “bad” for $q=1/2$. This seems to suggest that such eigenvalues can actually cause instabilities/issues with length generalization and are not limitations of our proof – if true, such a fact could be seen as a partial converse to Theorem 6 and would justify our use of “bad” to describe these eigenvalues. 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 in Figure 4. These results confirm that (some subset of) this bad region is indeed what throws off the length generalization capability of spectral filtering(^2^22Note that these plots are zoomed in to inspect the convergence to a loss of exactly 0; in practice, loss values below $0.1$ are still meaningfully small.).

Figure: Figure 3: Prediction losses $\ell_{t}(M^{t},T^{q})$ as a function of $t$ on an LDS with eigenvalues sampled from Region A, averaged over random seeds and smoothed.
Refer to caption: extracted/5972412/figs/online_lds_losses_region=A_opt=adam.png

### 5.2 Two Autoregressive Components

We have seen, both in theory and experiment, that vanilla spectral filtering has an inherent length generalization capability on an LDS under a minor spectral assumption. Introducing a second autoregressive component yields Algorithm 2, which is accompanied by a length generalization guarantee that removes this assumption and applies to all (symmetric, marginally-stable) LDS’s. We verify this experimentally in Figure 5 – to be as adversarial as we can, this experiment is run with all eigenvalues sampled from Region B. As predicted by Theorem 7, the second autoregressive component allows for robust length generalization even with context lengths as small as $\sqrt{T}$(^3^33The exact same conclusions are true for the tensorized version of the spectral filtering algorithm: the ”bad” eigenvalues cause problems if only $y_{t-1}$ is used, and introducing $y_{t-2}$ allows for complete length generalization under no spectral assumptions. The regression on $u_{t-1}$ and $u_{t-2}$ appears to make no difference in practice.).

Figure: Figure 5: Prediction losses $\ell_{t}(M^{t},T^{q})$ as a function of $t$ with two autoregressive components on an LDS with eigenvalues sampled from Region B, averaged over random seeds and smoothed. Contrast with Figure 4.
Refer to caption: extracted/5972412/figs/online_lds_losses_pasttwo_region=B_opt=adam.png

### 5.3 Induction Heads

So far, we have demonstrated length generalization of spectral filtering on linear systems: when trained with a shorter context length of $T^{q}$ it is able to compete with methods that have access to the full context $T$ (even on marginally-stable 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 nonlinearities) to solve non-LDS sequence prediction tasks.

As an empirical proof-of-concept to demonstrate that STU’s length generalization capability extends to this regime, we evaluate it on the induction heads synthetic sequence modeling task, which is commonplace in the language modeling literature (see Gu & Dao ())
and was experimentally shown in Liu et al. () 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 vocabulary) immediately after a special flag token; the rest of the sequence consists of the same special blank token, which the model should learn to ignore.

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 et al. ()) with filters of length $T=256$.

Following prior STU architecture implementations we use no autoregressive components, and so any length generalization observed here comes directly from the filtering mechanism itself. We train these models until convergence with a tuned Adam optimizer and various context lengths $T^{q}$. The vocabulary size is set to 4.

Figure: Figure 6: Accuracies for STU models trained on an induction heads task of length $T^{q}$ and evaluated on sequence lengths increasing up to $T$, averaged over random seeds. Models occasionally generalize all the way up to length $T$, as indicated by the large variance of evaluation accuracies.
Refer to caption: extracted/5972412/figs/inductionheads_lengthgen.png

Accuracies are plotted in Figure 6 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 very inconsistently. Importantly, unlike algorithms that achieve length generalization through architectural modification, we simply just train with filters longer than the train context(^4^44For example, the nonlinear selection mechanism of Gu & Dao () allows for extreme length generalization on induction heads without prior knowledge of the evaluation length, though at a cost to training efficiency, implementation simplicity, and optimization complexity. We reiterate that our goal is not to navigate such a tradeoff by modifying the STU model so that it length generalizes on induction heads, but rather to exhibit a provable length generalization capability of the STU that comes for free from its natural structure.). 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. ().

### 5.4 Tensorized STU Models

On the LDS, tensorization made no difference in terms of length generalization capabilities. Intuitively, however, the tensor representation does have a natural structure that seems conducive to length generalization. The same machinery (the first tensor component) is shared when learning the system’s evolution over each chunk of size $\sqrt{T}$, and the second tensor component simply aggregates the responses from these chunks. Crucially, the tensorized model is more expressive than an LDS since it does not require the tensor components to learn the pair $(\alpha,\alpha^{\sqrt{T}})$ but instead allows any $(\alpha,\beta)$ pair. In other words, the tensorized model is free to decouple how it gathers information within the chunks from how it synthesizes information across chunks. This extra expressitivity is unnecessary to succeed on an LDS, but turns out to matter on more complex nonlinear tasks, which we now investigate.

We repeat the experimental setup of the previous subsection, with the architectural difference that we replace the $k$ many filters of length $256$ with $k^{2}$ many filters of length $256$ formed from tensor combinations with components of length $16$. Note that although we increase the size of our filter bank from $k$ to $k^{2}$, this does not change the number of convolutions due to the tensordot approximation (see Liu et al. () for details).

In addition to induction heads, we also experiment on a copy task Arjovsky et al. (). This is a nonlinear sequence-to-sequence prediction task in which a fixed number of tokens are randomly sampled from a vocabulary and placed at the beginning of the input sequence, with blank tokens filling the rest of the sequence – the model must recall (in order) the initial non-blank tokens. We use a vocabulary size of 4 and fill $\frac{2}{3}$ of each input sequence with blank tokens.

In Figures 8 and 8 we plot the length generalization results on induction heads and copy, respectively, for both the vanilla STU and the variant with tensorized filters. We see that the tensorized model improves in both cases, with greater benefit at more extreme length generalizations (i.e. at smaller $q$). On the copy task in particular, it seems tensorization allows for near-perfect length generalization which the vanilla STU model cannot accomplish. This makes sense given the nature of the task: if we imagine splitting the filters into chunks of size $\sqrt{T}$, the issue is that tokens to be copied fall on different chunks during training and evaluation. The shared computation and extra expressivity of the tensorized model addresses this gap perfectly, allowing for the solution that is learned on a short instance of the task to be deployed on larger ones. By contrast, even though the vanilla STU model is able to ”see” the whole input during evaluation (because it has filter length 256), it is unable to length generalize (or even learn easily at long lengths given full context, as the dotted $T^{1}$ curve shows).

Figure: Figure 7: Length generalization on induction heads. Experiments with tensorized filters are bolded, while those without are dotted. Averaged over random seeds.
Refer to caption: extracted/5972412/figs/inductionheads_lengthgen_tensorized.png

As before, we remark that tensorized filters are not a substantial change to the regular STU architecture, but only a different set of filters to convolve against: such a model still retains favorable training efficiency via convolutions, optimization simplicity, etc.. This empirical result of improved length generalization via tensorization is not yet explained by theory, but in a sense it also seems to ”comes for free” with this construction of tensorized spectral filters. We conjecture the improved performance comes from the more expressive architecture, since standard filters are strictly contained in tensorized filters. We leave a more rigorous explanation of this phenomenon and experiments at larger scales for future work.

## 6 Discussion

In review, we first introduced the notion of Asymmetric-Regret as a 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 predictors naturally enjoys sublinear Asymmetric-Regret  thereby exhibiting length generalization without any change to the algorithm. Next, we used experiments on synthetic data generated by an LDS to demonstrate the validity and sharpness of our theory and provided proof-of-concept length generalization experiments on a synthetic nonlinear sequence prediction task. Finally, we made use of the tensor structure inherent in LDS’s to design a more expressive tensorized spectral filtering algorithm, which empirically boosted length generalization on our synthetic nonlinear tasks.

Our theoretical results and initial empirical findings reveal that some type of length generalization comes naturally with the spectral filtering algorithm. This adds to the already-exciting list of its useful (and provable) properties, including: robustness to systems with long memory and large hidden dimension, efficient training via convolutions, optimization convexity, and the existence of very parameter-efficient approximations. Given recent successful applications of spectral filtering as the building block for STU models in deep learning (Agarwal et al., ; Liu et al., ), it would be valuable to research how to best take advantage of their length generalization capacity at scale – we leave this for future work.

## Appendix A General Length Generalization

In this section we introduce a general algorithm which we will use to prove length generalization for our specific Algorithms Algorithm 1, Algorithm 2, and Algorithm 3.

Figure: Algorithm 4 General Spectral Filtering

Our workhorse theorem is presented below. We will use this theorem to prove length generalization for our special cases in the following sections.

###### Theorem 11 .

Suppose $y_{1:t}$ evolves as a noiseless $(A,B,C,I)$-LDS and the input $u_{(t-1):0}$ is such that $\sum_{t=0}^{T-1}(T-t)u_{t}u_{t}^{\top}\succeq(2\|C\|\|B\|/\sqrt{T})I$. Let $k$, $L$, $r$, $\{v_{i}\}_{i=1}^{k}$, $p_{t}(\cdot)$, and $\ell_{t}(\cdot)$ all be as defined in Algorithm 4. Suppose $\{v_{i}\}_{i=1}^{k}$ is orthonormal with $\|v_{i}\|_{1}~{}\leq~{}\log^{p}(T)$. Suppose that $p_{t}(\cdot)$ is such that there exists some function $h(\cdot)$, constant $\ell>0$, and some $M^{\textrm{true}}\in\mathcal{K}_{r}$ such that

$$ $y_{t}-p_{t}(y_{t-1:1})=\sum_{i=1}^{T}M^{\textrm{true}}_{i}u_{t-1:0}v_{i}=\sum_ {i=1}^{\ell_{1}}M^{\textrm{true}}_{i}u_{t-i}+\sum_{i=1}^{t-\ell_{1}}CA^{i}h(A) Bu_{t-\ell_{1}-i},$ $$

where

$$ $\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{t-1:t-L}v_{i}\|~{}\leq~{}\|C\|\|B\|/T,$ $$

and

$$ $\max_{\alpha(A)}\left\{h(\alpha)\alpha^{L-\ell_{1}-1}(1-\alpha^{T-L+1})(1- \alpha)^{-1}\right\}~{}\leq~{}\frac{1}{T^{1/4}}.$ $$

Then if $M^{t}$ are the iterates of Algorithm 4 and $T~{}\geq~{}(4k\log^{p}(T)/\|C\|\|B\|)^{4}$,

$$ $\sum_{t=1}^{T}\ell_{t}(M^{t},L)-\min_{M^{*}\in\mathcal{K}_{r}}\sum_{t=1}^{T} \ell_{t}(M^{*},T)~{}\leq~{}\left(12k^{3/2}r^{2}\log^{p}(T)+8\|C\|^{2}\|B\|^{2} \right)\sqrt{T}.$ $$

The proof of this theorem requires several technical lemmas which we present and prove in the subsequent subsections. In Lemma 12 we essentially prove the standard result showing that Online Gradient Descent implemented in Algorithm 4 achieves $O(\sqrt{T})$ regret. In Lemma 13 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 $L$. Combining these two lemmas gives the proof of Theorem 11.

###### Proof of Theorem 11 .

Let

$$ $M_{T}^{*}\stackrel{{\scriptstyle\text{def}}}{{=}}\min_{M^{*}\in\mathcal{K}_{r} }\sum_{t=1}^{T}\ell_{t}(M^{*},T)$ $$

and observe that

$$ $\displaystyle\min_{M^{*}\in\mathcal{K}_{r}}\sum_{t=1}^{T}\ell_{t}(M^{*},L)~{} \leq~{}\sum_{t=1}^{T}\ell_{t}(M^{*}_{T},L).$ (9) $$

Combining this with Lemma 12 and Lemma 13, we conclude

$$ $\displaystyle\sum_{t=1}^{T}\ell_{t}(M_{t},L)$ $\displaystyle~{}\leq~{}\min_{M^{*}\in\mathcal{K}_{r}}\sum_{t=1}^{T}\ell_{t}(M^ {*},L)+12k^{3/2}r^{2}\log^{p}(T)\sqrt{T}$ OGD Regret Lemma 12 $\displaystyle~{}\leq~{}\sum_{t=1}^{T}\ell_{t}(M^{*}_{T},L)+12k^{3/2}r^{2}\log^ {p}(T)\sqrt{T}$ Eq. 9 $\displaystyle~{}\leq~{}\sum_{t=1}^{T}\ell_{t}(M^{*}_{T},T)+(12k^{3/2}r^{2}\log ^{p}(T)+8\|C\|^{2}\|B\|^{2})\sqrt{T}$ Length Generalization Lemma 13 $\displaystyle=\min_{M^{*}\in\mathcal{K}_{r}}\sum_{t=1}^{T}\ell_{t}(M,T)+(12k^{ 3/2}r^{2}\log^{p}(T)+8\|C\|^{2}\|B\|^{2})\sqrt{T}.$ Definition of $M_{T}^{*}$ $$

∎

###### Theorem 11 .

###### Proof of Theorem 11 .

### A.1 OGD Regret for Generalized Spectral Filtering

###### Lemma 12 .

Suppose the input $u_{1:t}$ satisfies $\|u_{t}\|_{2}~{}\leq~{}1$. Suppose the true output $y_{t}$ evolves such that for some polynomial $p_{t}(y_{t-1:1})$ there exists some $M^{\textrm{true}}\in\mathcal{K}_{r}$

$$ $y_{t}=p_{t}(y_{t-1:1})+\sum_{i=1}^{T}M^{\textrm{true}}_{i}u_{t-1:0}v_{i},$ $$

and for

$$ $E_{m,T}\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{i=k+1}^{T}M^{\textrm{true }}_{i}u_{t-1:0}v_{i},$ $$

we have $\|E_{m,T}\|~{}\leq~{}1$. Further suppose $v_{1},\dots,v_{k}$ satisfy $\|v_{i}\|_{1}~{}\leq~{}c_{i}\log^{p}(T)$. Let

$$ $\ell_{t}(M,L)\stackrel{{\scriptstyle\text{def}}}{{=}}\|y_{t}-p_{t}(y_{t-1:1})- \sum_{i=1}^{k}M_{i}u_{t-1:t-L}v_{i}\|^{2},$ $$

Then if $M^{t}$ are the iterates of Algorithm 4

$$ $\sum_{t=1}^{T}\ell_{t}(M^{t},L)-\min_{M^{*}\in\mathcal{K}_{r}}\sum_{t=1}^{T} \ell_{t}(M^{*},L)~{}\leq~{}12k^{3/2}r^{2}\log^{p}(T)\sqrt{T}.$ $$

###### Proof of Lemma 12 .

This proof is a near copy of the proof in Hazan et al. (), the difference is that we derive several equations that we will use later and we handle the varying context length.

Let $G=\max_{t\in[T]}\|\nabla\mkern-2.5mu_{M}\ell_{t}(M_{t},L)\|$ and let $D=\max_{M_{1},M_{2}\in\mathcal{K}_{r}}\|M_{1}-M_{2}\|$. By Theorem A.1 from Hazan & Singh (),

$$ $\sum_{t=1}^{T}\ell_{t}(M^{t},L)-\min_{M^{*}\in\mathcal{K}_{r}}\sum_{t=1}^{T} \ell_{t}(M^{*},L)~{}\leq~{}\frac{3}{2}GD\sqrt{T}.$ $$

Therefore it remains to bound $G$ and $D$.

First we bound $D$. By definition of $\mathcal{K}_{r}$, we have that for any $M\in\mathcal{K}_{r}$,

$$ $\|M_{i}\|~{}\leq~{}r.$ $$

Therefore, we also have that

$$ $\|M\|~{}\leq~{}\sqrt{k}r.$ $$

Therefore

$$ $D\stackrel{{\scriptstyle\text{def}}}{{=}}\max_{M,M^{\prime}\in\mathcal{K}_{r}} \|M-M^{\prime}\|~{}\leq~{}2\sqrt{k}r.$ $$

Next we bound the gradient norm $G$. Using the definition of $\mathcal{K}_{r}$,

$$ $\displaystyle\max_{M\in\mathcal{K}_{r}}\max_{i\in[k]}\|M_{i}\|~{}\leq~{}r.$ $$

We bound the gradient norm as follows,

$$ $\displaystyle\|\nabla\mkern-2.5mu_{M_{j}}\ell_{t}(M,L)\|$ $\displaystyle=\|2\left(\sum_{i=1}^{k}M^{\textrm{true}}_{i}u_{t-1:0}v_{i}+E_{m, T}-\sum_{i=1}^{k}M_{i}u_{t-1:t-L}v_{i}\right)\left(u_{t-1:t-L}v_{j}\right)^{ \top}\|$ $\displaystyle~{}\leq~{}2\left(\sum_{i=1}^{k}\|M^{\textrm{true}}_{i}\|\|u_{t-1: 0}\|_{\infty}\|v_{i}\|_{1}+\|E_{m,T}\|+\sum_{i=1}^{k}\|M_{i}\|\|u_{t-1:t-L}\|_ {\infty}\|v_{i}\|_{1}\right)\|u_{t:t-L}\|_{\infty}\|v_{j}\|_{1}$ $\displaystyle~{}\leq~{}2\left(1+\|E_{m,T}\|\right)\sum_{i=1}^{k}\max_{M\in \mathcal{K}_{r}}\|M_{i}\|\cdot\|u_{t-1:0}\|_{\infty}^{2}\cdot\|v_{i}\|_{1}^{2}$ $\displaystyle~{}\leq~{}4kr\log^{p}(T).$ $$

Putting everything together we have

$$ $\displaystyle\sum_{t=1}^{T}\ell_{t}(M_{t},L)-\min_{M^{*}\in\mathcal{K}_{r}} \sum_{t=1}^{T}\ell_{t}(M^{*},L)$ $\displaystyle~{}\leq~{}\frac{3}{2}\left(4kr\log^{p}(T)\right)\left(2\sqrt{k}r \right)\sqrt{T}$ $\displaystyle=12k^{3/2}r^{2}\log^{p}(T)\sqrt{T}.$ $$

∎

###### Lemma 12 .

###### Proof of Lemma 12 .

### A.2 Length Generalization on the Best Optimizer in Hindsight

###### Lemma 13 .

Let input $u_{(t-1):0}$, $\{v_{i}\}_{i=1}^{k}$, $p_{t}(\cdot)$, and $\ell_{t}(M,L)$ all be as defined in Algorithm 4. Suppose the input $u_{(t-1):0}$ is such that $\sum_{t=0}^{T-1}(T-t)u_{t}u_{t}^{\top}\succeq(2\|C\|\|B\|/\sqrt{T})I$, $\{v_{i}\}_{i=1}^{k}$ is orthonormal with $\|v_{i}\|_{1}~{}\leq~{}\log^{p}(T)$, and that there exists some $M^{\textrm{true}}$ such that

$$ $y_{t}-p_{t}(y_{t-1:1})=\sum_{i=1}^{T}M^{\textrm{true}}_{i}u_{t-1:0}v_{i}=\sum_ {i=1}^{\ell_{1}}M^{\textrm{true}}_{i}u_{t-i}+\sum_{i=1}^{t-\ell_{1}-1}CA^{i}h( A)Bu_{t-\ell_{1}-i},$ $$

where

$$ $\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{t-1:t-L}v_{i}\|~{}\leq~{}\|C\|\|B\|/T,$ $$

and

$$ $\max_{\alpha(A)}\left\{h(\alpha)\alpha^{L-\ell_{1}-1}(1-\alpha^{T-L+1})(1- \alpha)^{-1}\right\}~{}\leq~{}\frac{1}{T^{1/4}}.$ $$

Let

$$ $M_{T}^{*}\stackrel{{\scriptstyle\text{def}}}{{=}}\operatorname*{arg\,min}_{M \in\mathcal{K}_{r}}\sum_{t=1}^{T}\ell_{t}(M,T).$ $$

Then for $T~{}\geq~{}(4k\log^{p}(T)/\|C\|\|B\|)^{4}$, the loss with context $L$ well approximates the loss with context $T$ on $M_{T}^{*}$,

$$ $|\sum_{t=1}^{T}\ell_{t}(M_{T}^{*},L)-\ell_{t}(M_{T}^{*},T)|~{}\leq~{}8\|C\|^{2 }\|B\|^{2}\sqrt{T}.$ $$

The proof of Lemma 13 requires two key helper lemmas which we develop in the following subsections. The first is Lemma 14 which establishes that when $y_{1:t}$ evolves as a noiseless LDS and if the input $u_{1:t}$ is sufficiently well-conditioned, then the minimizer for $\sum_{t=1}^{T}\ell_{t}(M,T)$ approximately recovers a collection of matrices (we denote as $M^{\textrm{true}}$) which is generated by the true linear dynamical system. The second key helper Lemma is Lemma 15 which establishes that an algorithm which uses the collection of matrices that are generated by the true linear dynamical system, i.e. $M^{\textrm{true}}$, is able to achieve small loss even when restricted to a small context-length $L<<T$. The proof of Lemma 13 combines these two insights to establish that this implies that the minimizer for $\sum_{t=1}^{T}\ell_{t}(M,T)$ also achieves small loss even when restricted to small context-length $L$.

###### Proof of Lemma 13 .

First we show that $M^{\textrm{true}}$ is a $(\|C\|^{2}\|B\|^{2}/T)$-approximate minimizer to $\sum_{t=1}^{T}\ell_{t}(M,T)$. Indeed,

$$ $\displaystyle\sum_{t=1}^{T}\ell_{t}(M^{\textrm{true}},T)$ $\displaystyle=\sum_{t=1}^{T}\|y_{t}-p_{t}(y_{t-1:1})-\sum_{i=1}^{k}M^{\textrm{ true}}_{i}u_{t-1:0}v_{i}\|^{2}$ $\displaystyle=\sum_{t=1}^{T}\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{t-1:0}v_ {i}\|^{2}$ $\displaystyle~{}\leq~{}\|C\|^{2}\|B\|^{2}/T.$ $$

By assumption $\sum_{t=0}^{T-1}(T-t)u_{t}u_{t}^{\top}\succeq(2\|C\|\|B\|/\sqrt{T})I$. Therefore, by Lemma 14 with $\epsilon=\|C\|\|B\|/\sqrt{T}$ we have

$$ $M_{T}^{*}\in\mathcal{B}_{\|C\|\|B\|/\sqrt{T}}\left(M^{\textrm{true}}\right).$ $$

Since we assumed $T~{}\geq~{}(4k\log^{p}(T)/\|C\|\|B\|)^{4}$ we have

$$ $\|C\|\|B\|/\sqrt{T}~{}\leq~{}\|C\|^{2}\|B\|^{2}/(4kT^{1/4}\log^{p}(T)).$ $$

Therefore by Lemma 15
we have

$$ $\sum_{t=1}^{T}\ell_{t}(M_{T}^{*},L)~{}\leq~{}4\|C\|^{2}\|B\|^{2}\sqrt{T}.$ $$

Moreover note that

$$ $0~{}\leq~{}\ell_{t}(M_{T}^{*},T)~{}\leq~{}\ell_{t}(M^{\textrm{true}},T)~{}\leq ~{}\|C\|^{2}\|B\|^{2}/T^{2}.$ $$

Combining these we conclude,

$$ $|\sum_{t=1}^{T}\ell_{t}(M_{T}^{*},L)-\sum_{t=1}^{T}\ell_{t}(M_{T}^{*},T)|~{} \leq~{}4\|C\|^{2}\|B\|^{2}\sqrt{T}+\|C\|^{2}\|B\|^{2}/T~{}\leq~{}8\|C\|^{2}\|B \|^{2}\sqrt{T}.$ $$

∎

###### Lemma 13 .

###### Proof of Lemma 13 .

#### A.2.1 Minimization is Recovery

###### Lemma 14 .

Suppose $\sum_{t=0}^{T-1}(T-t)u_{t}u_{t}^{\top}\succeq 2\epsilon I$ and $\{v_{i}\}_{i=1}^{k}$ is orthonormal. Then there is a unique point $M^{*}$ which minimizes the function $\sum_{t=1}^{T}\ell_{t}(M,T)$ from Algorithm 4. Moreover, suppose some $k$ satisfies

$$ $\sum_{t=1}^{T}\ell_{t}(M,T)~{}\leq~{}\epsilon^{2}.$ $$

Then there is a matrix $E_{M}$ such that $\|E_{M}\|~{}\leq~{}\epsilon$ and

$$ $M^{*}=M+E_{M}.$ $$

###### Proof.

For convenience, let $X_{t}$ be the $kd_{\mathrm{in}}$-dimensional vector which stacks the filters,

$$ $X_{t}=\begin{bmatrix}u_{t-1:t-T}v_{1}\\ u_{t-1:t-T}v_{2}\\ \vdots\\ u_{t-1:t-T}v_{k}\end{bmatrix}=\begin{bmatrix}u_{t-1:0}v_{1}\\ u_{t-1:0}v_{2}\\ \vdots\\ u_{t-1:0}v_{k}\end{bmatrix},$ $$

where the second inequality holds since we only consider $t~{}\leq~{}T$.
Assume $k$ is written as $M=\begin{bmatrix}M_{1}&M_{2}&\dots&M_{k}\end{bmatrix}\in\mathbb{R}^{d_{\mathrm
{out}}\times kd_{\mathrm{in}}}$ and let $Y_{t}=y_{t}-p_{t}(y_{t-1:1})$. Let $Y=\begin{bmatrix}Y_{1}&Y_{2}&\dots&Y_{T}\end{bmatrix}$ and $X=\begin{bmatrix}X_{1}&X_{2}&\dots&X_{T}\end{bmatrix}$. Then we can express the loss as

$$ $f(M)\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{t=1}^{T}\ell_{t}(M,T)=\|Y-MX \|^{2}.$ $$

Note that this function is twice differentiable and

$$ $\nabla\mkern-2.5mu^{2}_{M}f(M)=XX^{\top}.$ $$

Therefore, if $\lambda_{\textrm{min}}\left(XX^{\top}\right)~{}\geq~{}\mu$ we have that $f(M)$ is $\mu$-strongly convex. Then if $M^{*}$ is the optimum of $f(M)$ we have

$$ $f(M)~{}\geq~{}f(M^{*})+\frac{\mu}{2}\|M-M^{*}\|^{2},\textrm{ or equivalently, }\|M-M^{*}\|~{}\leq~{}\frac{2}{\mu}\left(f(M)-f(M^{*})\right).$ $$

Now suppose $k$ is such that $f(M)~{}\leq~{}\epsilon^{2}$. Then since $f(\cdot)~{}\geq~{}0$ we have

$$ $\|M-M^{*}\|~{}\leq~{}2\epsilon^{2}/\mu.$ $$

Therefore we can write

$$ $M^{*}=M+E_{M^{*}}\textrm{ where }\|E_{M^{*}}\|~{}\leq~{}2\epsilon^{2}/\mu.$ (10) $$

Next we must understand the eigenvalues of $XX^{\top}$ and how they relate to the input $u_{T:1}$. For notational convenience, let $U=u_{T:1}$ and let $D_{t}$ denote the block-diagonal $T\times T$ matrix

$$ $D_{t}\stackrel{{\scriptstyle\text{def}}}{{=}}\begin{bmatrix}0_{T-t\times T-t}& \\ &I_{t}\end{bmatrix}.$ $$

Finally, let

$$ $V=\begin{bmatrix}v_{1}\\ v_{2}\\ \vdots\\ v_{k}\end{bmatrix}\in{\mathcal{R}}^{Tm\times 1}$ $$

Then we have $X_{t}=\left(I_{k}\otimes UD_{t}\right)V$ and we observe

$$ $\displaystyle XX^{\top}$ $\displaystyle=\sum_{t=1}^{T}X_{t}X_{t}^{\top}=\sum_{t=1}^{T}\left((I_{k} \otimes UD_{t})V\right)\left((I_{k}\otimes UD_{t})V\right)^{\top}$ $\displaystyle=\sum_{t=1}^{T}(I_{k}\otimes UD_{t}U^{\top})$ $\displaystyle=I_{k}\otimes U\left(\sum_{t=1}^{T}D_{t}\right)U^{\top}.$ $$

Observe that

$$ $\sum_{t=1}^{T}D_{t}=\mathrm{diag}\left(\begin{bmatrix}1&2&\dots&T\end{bmatrix} \right).$ $$

Using this we can further refine

$$ $\displaystyle U\left(\sum_{t=1}^{T}D_{t}\right)U^{\top}$ $\displaystyle=\sum_{t=0}^{T-1}(T-t)u_{t}u_{t}^{\top}.$ $$

By assumption, this matrix has minimum eigenvalue bounded below by $2\epsilon$. Therefore $\lambda_{\textrm{min}}(XX^{\top})~{}\geq~{}2\epsilon$. Plugging this value in for $\mu$ in Eq. 10 concludes the proof.

∎

###### Lemma 14 .

###### Proof.

#### A.2.2 Uniform Length Generalization Around LDS Generated Solutions

The following lemma shows that any $k$ in an (appropriately defined) $\epsilon$-ball around $M^{\textrm{true}}$ obtains length generalization in the sense that it achieves $O(\sqrt{T})$ $L$-context-length-limited loss $\sum_{t=1}^{T}\ell_{t}(\cdot,L)$.

###### Lemma 15 .

Suppose $y_{t}$ evolves as a noiseless $(A,B,C,I)$-LDS with input $u_{t}$. Suppose $p_{t}(\cdot)$ and $M^{\textrm{true}}$ is such that

$$ $y_{t}-p_{t}(y_{t-1:1})=\sum_{i=1}^{T}M^{\textrm{true}}_{i}u_{t-1:0}v_{i}=\sum_ {i=1}^{\ell_{1}}M^{\textrm{true}}_{i}u_{t-i}+\sum_{i=1}^{t-\ell_{1}-1}CA^{i}h( A)Bu_{t-\ell_{1}-i}.$ $$

Suppose for a given $k>0$,

$$ $\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{t-1:t-L}v_{i}\|~{}\leq~{}\frac{\|C\| \|B\|}{T}.$ $$

Suppose

$$ $\max_{\alpha(A)}\left\{h(\alpha)\alpha^{L-\ell_{1}-1}(1-\alpha^{T-L+1})(1- \alpha)^{-1}\right\}~{}\leq~{}\frac{1}{T^{1/4}}.$ $$

If

$$ $\delta~{}\leq~{}\frac{1}{4m}\frac{\|C\|^{2}\|B\|^{2}}{T^{1/4}\log^{p}(T)},$ $$

then we have for any $M\in\mathcal{B}_{\delta}(M^{\textrm{true}})$

$$ $\sum_{t=1}^{T}\ell_{t}(M,L)~{}\leq~{}4\|C\|^{2}\|B\|^{2}\sqrt{T}.$ $$

###### Proof of Lemma 15 .

Let $M=M^{\textrm{true}}+E_{M}$, where $\|E_{M}\|~{}\leq~{}\delta$. By definition,

$$ $\displaystyle\ell_{t}(M^{\textrm{true}}+E_{M},L)$ $\displaystyle=\|y_{t}-p_{t}(y_{t-1:1})-\sum_{i=1}^{k}\left(M^{\textrm{true}}+E _{M}\right)_{i}u_{t-1:t-L}v_{i}\|^{2}$ $\displaystyle=\|y_{t}-p_{t}(y_{t-1:1})-\sum_{i=1}^{k}M^{\textrm{true}}_{i}u_{t -1:t-L}v_{i}-\sum_{i=1}^{k}E_{M_{i}}u_{t-1:t-L}v_{i}\|^{2}$ $\displaystyle~{}\leq~{}\|y_{t}-p_{t}(y_{t-1:1})-\sum_{i=1}^{k}M^{\textrm{true} }_{i}u_{t-1:t-L}v_{i}\|^{2}$ $\displaystyle\qquad+2\|y_{t}-p_{t}(y_{t-1:1})-\sum_{i=1}^{k}M^{\textrm{true}}_ {i}u_{t-1:t-L}v_{i}\|\|\sum_{i=1}^{k}E_{M_{i}}u_{t-1:t-L}v_{i}\|$ $\displaystyle\qquad+\|\sum_{i=1}^{k}E_{M_{i}}u_{t-1:t-L}v_{i}\|^{2}.$ $$

Observe that

$$ $\displaystyle\|\sum_{i=1}^{k}E_{M_{i}}u_{t-1:t-L}v_{i}\|$ $\displaystyle~{}\leq~{}\sum_{i=1}^{k}\|E_{M_{i}}\|\|u_{t-1:t-L}\|_{\infty}\|v_ {i}\|_{1}~{}\leq~{}k\delta\log^{p}(T).$ $$

For the remainder of the proof we work towards bounding $\|y_{t}-p_{t}(y_{t-1:1})-\sum_{i=1}^{k}M^{\textrm{true}}_{i}u_{t-1:t-L}v_{i}\|$.
We replace $y_{t}-p_{t}(y_{t-1:1})$ with $\sum_{i=1}^{T}M^{\textrm{true}}_{i}u_{t-1:0}v_{i}$ and we replace $\sum_{i=1}^{k}M^{\textrm{true}}_{i}u_{t-1:t-L}v_{i}$ with $\sum_{i=1}^{T}M^{\textrm{true}}_{i}u_{t-1:t-L}v_{i}-\sum_{i=k+1}^{T}M^{\textrm
{true}}_{i}u_{t-1:t-L}v_{i}$ to get

$$ $\displaystyle\|y_{t}-p_{t}(y_{t-1:1})-\sum_{i=1}^{k}M^{\textrm{true}}_{i}u_{t- 1:t-L}v_{i}\|^{2}$ $\displaystyle=\|\left(\sum_{i=1}^{T}M^{\textrm{true}}_{i}u_{t-1:0}v_{i}\right) -\left(\sum_{i=1}^{T}M^{\textrm{true}}_{i}u_{t-1:t-L}v_{i}-\sum_{i=k+1}^{T}M^{ \textrm{true}}_{i}u_{t-1:t-L}v_{i}\right)\|^{2}$ $\displaystyle~{}\leq~{}\|\sum_{i=1}^{T}M^{\textrm{true}}_{i}(u_{t-1:0}-u_{t-1: t-L})v_{i}\|^{2}$ $\displaystyle\qquad+2\|\sum_{i=1}^{T}M^{\textrm{true}}_{i}(u_{t-1:0}-u_{t-1:t- L})v_{i}\|\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{t-1:t-L}v_{i}\|$ $\displaystyle\qquad+\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{t-1:t-L}v_{i}\|^ {2}.$ $$

Next we note that $\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{t-1:t-L}v_{i}\|$ is assumed to be at most $\|C\|\|B\|/T$ and so we now focus on bounding the norm:

$$ $\|\sum_{i=1}^{T}M^{\textrm{true}}_{i}(u_{t-1:0}-u_{t-1:t-L})v_{i}\|.$ (11) $$

Towards bounding Eq. 11, assume $L>\ell_{1}$ so that

$$ $\displaystyle\sum_{i=1}^{T}M^{\textrm{true}}_{i}(u_{t-1:0}-u_{t-1:t-L})v_{i}$ $\displaystyle=\sum_{i=L-\ell_{1}+1}^{t-\ell_{1}-1}CA^{i}h(A)Bu_{t-\ell_{1}-i}$ $\displaystyle=\sum_{i=L-\ell_{1}+1}^{t-\ell_{1}-1}\sum_{j=1}^{d_{A}}\alpha_{j} ^{i}h(\alpha_{j})C_{j}B_{j}^{\top}u_{t-\ell_{1}-i}.$ $$

Then

$$ $\displaystyle\|\sum_{i=L-\ell_{1}+1}^{t-\ell_{1}-1}CA^{i}h(A)Bu_{t-\ell_{1}-i}\|$ $\displaystyle~{}\leq~{}\max_{j\in[d_{A}]}\alpha_{j}^{i}h(\alpha_{j})\sum_{i=L- \ell_{1}+1}^{t-\ell_{1}-1}\|C_{j}B_{j}^{\top}u_{t-\ell_{1}-i}\|$ $\displaystyle~{}\leq~{}\max_{\alpha(A)}\sum_{i=L-\ell_{1}+1}^{t-\ell_{1}-1} \alpha^{i}h(\alpha)\|C\|\|B\|.$ $$

Next we have

$$ $\displaystyle\left(\max_{\alpha(A)}\sum_{i=L-\ell_{1}+1}^{t-\ell_{1}-1}\alpha^ {i}h(\alpha)\right)$ $\displaystyle~{}\leq~{}h(\alpha)\alpha^{L-\ell_{1}-1}\sum_{i=0}^{T-L}\alpha^{i}$ $\displaystyle=h(\alpha)\alpha^{L-\ell_{1}-1}\frac{1-\alpha^{T-L+1}}{1-\alpha}$ $\displaystyle~{}\leq~{}T^{-1/4},$ $$

where the last inequality holds by assumption. Therefore Eq. 11 is at most

$$ $\displaystyle\|\sum_{i=1}^{T}M^{\textrm{true}}_{i}(u_{t-1:0}-u_{t-1:t-L})v_{i} \|~{}\leq~{}\|C\|\|B\|T^{-1/4}.$ $$

Then we have

$$ $\displaystyle\|y_{t}-p_{t}(y_{t-1:1})-\sum_{i=1}^{k}M^{\textrm{true}}_{i}u_{t- 1:t-L}v_{i}\|^{2}$ $\displaystyle~{}\leq~{}\frac{\|C\|^{2}\|B\|^{2}}{T^{1/2}}+2\frac{\|C\|^{2}\|B \|^{2}}{T^{3/4}}+\frac{\|C\|^{2}\|B\|^{2}}{T^{2}}~{}\leq~{}2\frac{\|C\|^{2}\|B \|^{2}}{T^{1/2}}.$ $$

Finally we conclude

$$ $\displaystyle\ell_{t}(M^{\textrm{true}}+E_{M},L)$ $\displaystyle~{}\leq~{}2\frac{\|C\|^{2}\|B\|^{2}}{T^{1/2}}+2\left(2\frac{\|C\| ^{2}\|B\|^{2}}{T^{1/2}}\right)^{1/2}\left(k\delta\log^{p}(T)\right)+\left(k \delta\log^{p}(T)\right)^{2}$ $\displaystyle~{}\leq~{}4\frac{\|C\|^{2}\|B\|^{2}}{T^{1/2}},$ $$

where the last inequality holds since we assumed

$$ $\delta~{}\leq~{}\frac{1}{4m}\frac{\|C\|^{2}\|B\|^{2}}{T^{1/4}\log^{p}(T)}.$ $$

∎

###### Lemma 15 .

###### Proof of Lemma 15 .

## Appendix B Length Generalization for Vanilla Spectral Filtering

The proof of Theorem 6 ultimately comes from Theorem 11 and its proof in Appendix A. Theorem 11 abstracts the necessary assumptions needed to obtain a length generalization guarantee. In Lemma 16 we prove that Algorithm 1 satisfies these assumptions.

###### Proof of Theorem 6 .

By Lemma 16 and the assumptions made in the statement of Theorem 6, we may apply Theorem 11 to Algorithm 1 to get that

$$ $\sum_{t=1}^{T}\ell_{t}(M^{t},L)-\min_{M^{*}\in\mathcal{K}_{\|C\|\|B\|}}\sum_{t =1}^{T}\ell_{t}(M^{*},T)~{}\leq~{}\left(12k^{3/2}\|C\|^{2}\|B\|^{2}\log(T)+8\| C\|^{2}\|B\|^{2}\right)\sqrt{T}.$ $$

∎

###### Lemma 16 (Length Generalization for Vanilla Spectral Filtering) .

Recall that in Algorithm 1 we define

$$ $\mu_{\alpha}\stackrel{{\scriptstyle\text{def}}}{{=}}(\alpha-1)\begin{bmatrix}1 &\alpha&\dots&\alpha^{T-1}\end{bmatrix}^{\top}\in\mathbb{R}^{T-1}$ $$

and $H_{T-1}=\int_{\alpha\in[0,1]}\mu_{\alpha}\mu_{\alpha}^{\top}d\alpha$ and we let $\phi_{1},\dots,\phi_{T-1}$ be the orthonormal eigenvectors of $H_{T-1}$ with eigenvalues $\sigma_{1},\dots,\sigma_{T-1}$.
Algorithm 1 is equivalent to Algorithm 4 with the following:

- (a)
$p_{t}(y_{t-1:1})=y_{t-1}$
- (b)
$v_{1}=e_{1}$
- (c)
$v_{i}=(0,\sigma_{i-1}^{1/4}\phi_{i-1})$ for $i=2,\dots,T$

Define $M^{\textrm{true}}$ as follows:

$$ $M^{\textrm{true}}_{1}\stackrel{{\scriptstyle\text{def}}}{{=}}CB,$ $$

and for $i~{}\geq~{}2$

$$ $M^{\textrm{true}}_{i}\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{n=1}^{d_{A} }\sigma_{i-1}^{-1/4}\phi_{i-i}^{\top}\mu_{\alpha_{n}}(C_{n}B_{n}^{\top}).$ $$

Then the following properties hold

- 1.
For $h(A)=A-I$ and $\ell_{1}=1$
$y_{t}-p_{t}(y_{t-1:1})=\sum_{i=1}^{\ell_{1}}M^{\textrm{true}}_{i}u_{t-i}+\sum_
{i=1}^{t-\ell_{1}}CA^{i}h(A)Bu_{t-\ell_{1}-i}.$
- 2.
$y_{t}-p_{t}(y_{t-1:1})=\sum_{i=1}^{T}M^{\textrm{true}}_{i}u_{t-1:1}v_{i}$.
- 3.
For $k=\Omega(\log(Td_{A}\|C\|\|B\|/\epsilon))$,
$\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{t-1:1}v_{i}\|~{}\leq~{}\epsilon/T.$
- 4.
For any $i\in[T]$
$\|M^{\textrm{true}}_{i}\|~{}\leq~{}\|C\|\|B\|.$
- 5.
For any $i\in[T]$, $\|v_{i}\|_{1}~{}\leq~{}\log(T)$ and $\{v_{i}\}_{i\in[T]}$ are orthonormal.
- 6.
Finally if the spectrum of $A$ lies in the interval
$\left[0,1-\frac{\log(T)}{2(L-2)}\right]\cup\left[1-\frac{1}{2T^{5/4}},1\right],$
then
$\max_{\alpha(A)}\left\{|h(\alpha)\alpha^{L-\ell_{1}-1}(1-\alpha^{T-L+1})(1-
\alpha)^{-1}|\right\}~{}\leq~{}\frac{1}{T^{1/4}}.$

###### Proof.

Points $(a)-(c)$ are evident by definition of Algorithm 1. Now suppose $y_{t}$ evolves as an LDS. By definition, there exist matrices $(A,B,C,D)$ such that

$$ $y_{t}=\sum_{i=1}^{t}CA^{i-1}Bu_{t-i},$ $$

where we assume $D=I$ and $A$ is diagonal without loss of generality. Let $\alpha_{1},\dots,\alpha_{d_{A}}$ denote the eigenvalues of $A$. and let $u_{t:0}$ be the $d_{\mathrm{in}}\times T$ (padded) matrix $u_{t:0}=\begin{bmatrix}u_{t}&u_{t-1}&\dots&u_{0}&0\end{bmatrix}$.
Then we have

$$ $\displaystyle y_{t}-y_{t-1}$ $\displaystyle=\sum_{i=1}^{t}CA^{i-1}Bu_{t-i}-\sum_{i=1}^{t-1}CA^{i-1}Bu_{t-1-i}$ $\displaystyle=CBu_{t-1}+\sum_{i=1}^{t-1}C\left(A^{i}-A^{i-1}\right)Bu_{t-1-i}.$ $$

We pause here to note this proves $(1)$. We continue rearranging the equation to finish the derivation of $(2)$.

$$ $\displaystyle y_{t}-y_{t-1}$ $\displaystyle=CBu_{t-1}+\sum_{i=1}^{t-1}C\left(A^{i}-A^{i-1}\right)Bu_{t-1-i}$ $\displaystyle=CBu_{t-1}+\sum_{n=1}^{d_{A}}Ce_{n}e_{n}^{\top}B\sum_{i=1}^{t-1} \left(\alpha_{n}^{i}-\alpha_{n}^{i-1}\right)u_{t-1-i}$ $\displaystyle=CBu_{t-1}+\sum_{n=1}^{d_{A}}(C_{n}B_{n}^{\top})u_{(t-2):0}\mu_{ \alpha_{j}}.$ $$

Observe that

$$ $\sum_{i=1}^{T-1}\phi_{i}\phi_{i}^{\top}=I.$ $$

Using this we have,

$$ $\displaystyle y_{t}-y_{t-1}$ $\displaystyle=CBu_{t-1}+\sum_{n=1}^{d_{A}}(C_{n}B_{n}^{\top})u_{(t-2):0}\mu_{ \alpha_{n}}$ $\displaystyle=CBu_{t-1}+\sum_{n=1}^{d_{A}}(C_{n}B_{n}^{\top})u_{(t-2):0}\left( \sum_{i=1}^{T}\phi_{i}\phi_{i}^{\top}\right)\mu_{\alpha_{n}}$ $\displaystyle=CBu_{t-1}+\sum_{i=1}^{T}\sum_{n=1}^{d_{A}}\phi_{i}^{\top}\mu_{ \alpha_{n}}(C_{n}B_{n}^{\top})u_{(t-2):0}\phi_{i}.$ $$

Recalling the definition of $M^{\textrm{true}}$ and $v_{i}=\sigma_{i-1}^{1/4}\phi_{i-1}$ we therefore have established $(2)$:

$$ $y_{t}-y_{t-1}=M^{\textrm{true}}_{1}u_{(t-1):0}e_{1}+\sum_{i=2}^{T-1}M^{\textrm {true}}_{i}u_{(t-1):0}v_{i}.$ $$

Next we aim to prove $(3)$. We consider

$$ $\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{(t-2):0}v_{i}\|.$ $$

By Lemma 13.4 in Hazan & Singh () there is some universal constant $c^{\prime}$ such that,

$$ $\max_{\alpha\in[0,1]}|\phi_{i}^{\top}\mu_{\alpha}|~{}\leq~{}c^{\prime}T^{2} \exp(-i/\log(T)).$ $$

So,

$$ $\displaystyle\|M^{\textrm{true}}_{i}u_{(t-2):0}v_{i}\|$ $\displaystyle=\|\sum_{n=1}^{d_{A}}\sigma_{i-1}^{-1/4}\phi_{i-i}^{\top}\mu_{ \alpha_{n}}(C_{n}B_{n}^{\top})u_{(t-2):0}\left(\sigma_{i-1}^{1/4}\phi_{i-1} \right)\|$ $\displaystyle=\|\sum_{n=1}^{d_{A}}\phi_{i-i}^{\top}\mu_{\alpha_{n}}(C_{n}B_{n} ^{\top})u_{(t-2):0}\phi_{i-1}\|$ $\displaystyle~{}\leq~{}d_{A}(c^{\prime}T^{2}\exp(-(i-1)/\log(T)))\|C_{n}B_{n}^ {\top}\|\|\phi_{i-1}\|_{1}$ $\displaystyle~{}\leq~{}c^{\prime}d_{A}T^{3/2}\exp(-(i-1)/\log(T)))\|C\|\|B\|.$ $$

Therefore,

$$ $\displaystyle\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{(t-1):0}\phi_{i}\|$ $\displaystyle~{}\leq~{}c^{\prime}d_{A}T^{5/2}\exp(-k/\log(T)))\|C\|\|B\|$ $$

Therefore as long as

$$ $k~{}\geq~{}\log(T)\log\left(\frac{T^{5/2}c^{\prime}d_{A}\|C\|\|B\|}{\epsilon} \right),$ $$

then

$$ $\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{(t-1):0}\phi_{i}\|~{}\leq~{}\frac{ \epsilon}{T}.$ $$

Next we note that the proof of $(4)$ that $\|M^{\textrm{true}}_{i}\|~{}\leq~{}\|C\|\|B\|$ is proven in Lemma D.1 of Hazan et al. (). Similarly, the proof of $(5)$ that $\|v_{i}\|_{1}~{}\leq~{}\log(T)$ is proven by Lemma 17 from Hazan et al. ().
Finally we prove $(6)$. Since $h(\alpha)=\alpha-1$ and $\ell_{1}=1$, we have

$$ $\displaystyle\max_{\alpha(A)}\left\{|h(\alpha)\alpha^{L-\ell_{1}-1}(1-\alpha^{ T-L+1})(1-\alpha)^{-1}|\right\}$ $\displaystyle=\max_{\alpha(A)}\alpha^{L-2}(1-\alpha^{T-L+1}).$ (12) $$

To bound Eq. 12, consider the case where $\alpha$ is bounded away from $1$. Suppose $\alpha=1-\delta$, then

$$ $\displaystyle(1-\delta)^{L-2}~{}\leq~{}\frac{1}{T^{p}}\iff\log\left(\frac{1}{1 -\delta}\right)~{}\geq~{}\frac{p\log(T)}{L-2}.$ $$

Observe that for $\delta\in[0,1]$, $\log(1/(1-\delta))~{}\geq~{}\delta/2$. Therefore, if

$$ $\displaystyle\delta~{}\geq~{}\frac{2p\log(T)}{L-2},$ $$

we are guaranteed that $\alpha^{L-2}~{}\leq~{}1/T^{p}$. Next consider when $\alpha$ is very close to $1$; suppose $\alpha~{}\geq~{}1-\frac{1}{T^{p}T}$ for $p<1/2$. Then using that $(1-x)^{q}~{}\geq~{}1-2qx$ for $x\in[0,1]$ we have

$$ $\alpha^{T-L+1}~{}\geq~{}\left(1-\frac{1}{T^{p}T}\right)^{T-L+1}~{}\geq~{}1-2 \frac{T-L+1}{T^{p}T}\implies 1-\alpha^{T-L+1}~{}\leq~{}2\frac{T-L+1}{T^{p}T}~{ }\leq~{}\frac{2}{T^{p}}.$ $$

Plugging in $p=1/4$ we conclude that

$$ $\alpha^{L-2}(1-\alpha^{T-L+1})~{}\leq~{}T^{-1/4}\qquad\textrm{ for any }\alpha \in\left[0,1-\frac{\log(T)}{2(L-2)}\right]\cup\left[1-\frac{1}{2T^{5/4}},1 \right].$ $$

∎

The following lemma comes from Hazan et al. ().

###### Lemma 17 (Hazan, Singh, Zhang) .

Let $(\sigma_{j},\phi_{j})$ be the $j$-th largest eigenvalue-eigenvector pair of the $T\times T$ Hankel matrix. Then,

$$ $\|\phi_{j}\|_{1}~{}\leq~{}O\left(\frac{\log(T)}{\sigma_{j}^{1/4}}\right).$ $$

###### Proof of Theorem 6 .

###### Lemma 16 (Length Generalization for Vanilla Spectral Filtering) .

###### Proof.

###### Lemma 17 (Hazan, Singh, Zhang) .

## Appendix C Length Generalization for Spectral Filtering Using Two Autoregressive Components

The proof of Theorem 7 ultimately comes from Theorem 11 and its proof in Appendix A. Theorem 11 abstracts the necessary assumptions needed to obtain a length generalization guarantee. In Lemma 18 we prove that Algorithm 2 satisfies these assumptions.

###### Proof of Theorem 7 .

By Lemma 18 and the assumptions made in the statement of Theorem 7, we may apply Theorem 11 to Algorithm 2 to get that

$$ $\sum_{t=1}^{T}\ell_{t}(M^{t},L)-\min_{M^{*}\in\mathcal{K}_{\|C\|\|B\|}}\sum_{t =1}^{T}\ell_{t}(M^{*},T)~{}\leq~{}\left(12k^{3/2}\|C\|^{2}\|B\|^{2}\log^{2}(T) +8\|C\|^{2}\|B\|^{2}\right)\sqrt{T}.$ $$

∎

###### Lemma 18 (Length Generalization Using Two Autoregressive Components) .

Recall that in Algorithm 2 we define

$$ $\tilde{\mu}_{\alpha,T}\stackrel{{\scriptstyle\text{def}}}{{=}}(\alpha-1)^{2} \begin{bmatrix}1&\alpha&\dots&\alpha^{T}\end{bmatrix}^{\top}\in\mathbb{R}^{T}$ $$

and
and $N_{T}=\int_{\alpha\in[0,1]}\tilde{\mu}_{\alpha,T}\tilde{\mu}_{\alpha,T}^{\top}d\alpha$ and we let $\tilde{\phi}_{1},\dots,\tilde{\phi}_{T-2}$ be the orthonormal eigenvectors of $N_{T-2}$ with eigenvalues $\tilde{\sigma}_{1},\dots,\tilde{\sigma}_{T-2}$.
Algorithm 2 is equivalent to Algorithm 4 with the following:

- (a)
$p_{t}(y_{t-1:1})=2y_{t-1}-y_{t-2}$
- (b)
$v_{1}=e_{1}$, $v_{2}=e_{2}$ and for $i~{}\geq~{}3$, $v_{i}=(0,0,\sigma_{i-2}^{1/4}\tilde{\phi}_{i-2})$

Define $M^{\textrm{true}}$ as follows:

$$ $M^{\textrm{true}}_{1}\stackrel{{\scriptstyle\text{def}}}{{=}}CB,$ $$

$$ $M^{\textrm{true}}_{2}\stackrel{{\scriptstyle\text{def}}}{{=}}C(A-2I)B,$ $$

and for $i~{}\geq~{}3$,

$$ $M^{\textrm{true}}_{i}\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{n=1}^{d_{A} }\left(\sigma_{i}^{-1/4}\tilde{\phi}_{i}^{\top}\tilde{\mu}_{\alpha_{n}}\right) (C_{n}B_{n}^{\top}).$ $$

Then the following properties hold

- 1.
For $h(A)=(A-I)^{2}$ and $\ell_{1}=2$
$y_{t}-p_{t}(y_{t-1:1})=\sum_{i=1}^{\ell_{1}}M^{\textrm{true}}_{i}u_{t-i}+\sum_
{i=1}^{t-\ell_{1}}CA^{i}h(A)Bu_{t-\ell_{1}-i}.$
- 2.
$y_{t}-p_{t}(y_{t-1:1})=\sum_{i=1}^{T}M^{\textrm{true}}_{i}u_{t-1:1}v_{i}$.
- 3.
For $k=\Omega(\log(Td_{A}\|C\|\|B\|/\epsilon))$,
$\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{t-1:1}v_{i}\|~{}\leq~{}\epsilon/T.$
- 4.
For any $i\in[T]$
$\|M^{\textrm{true}}_{i}\|~{}\leq~{}\|C\|\|B\|.$
- 5.
For any $i\in[T]$, $\|v_{i}\|_{1}~{}\leq~{}\log(T)$ and $\{v_{i}\}_{i\in[T]}$ are orthonormal.
- 6.
Finally if the spectrum of $A$ lies in the interval
$\left[0,1-\frac{\log(T)}{2(L-2)}\right]\cup\left[1-\frac{1}{2T^{1/4}},1\right],$
then
$\max_{\alpha(A)}\left\{|h(\alpha)\alpha^{L-\ell_{1}-1}(1-\alpha^{T-L+1})(1-
\alpha)^{-1}|\right\}~{}\leq~{}\frac{1}{T^{1/4}}.$

###### Proof.

Suppose $y_{t}$ evolves as an LDS. By definition, there exist matrices $(A,B,C,D)$ such that

$$ $y_{t}=\sum_{i=1}^{t}CA^{i-1}Bu_{t-i},$ $$

where we assume $D=I$ and $A$ is diagonal without loss of generality. Let $\alpha_{1},\dots,\alpha_{d_{A}}$ denote the eigenvalues of $A$. and let $u_{t:0}$ be the $d_{\mathrm{in}}\times T$ (padded) matrix $u_{t:0}=\begin{bmatrix}u_{t}&u_{t-1}&\dots&u_{0}&0\end{bmatrix}$.
Then we have $(1)$:

$$ $\displaystyle y_{t}-2y_{t-1}+y_{t-2}$ $\displaystyle=CBu_{t-1}+C(A-2I)Bu_{t-2}+\sum_{i=0}^{t-3}CA^{i}(A^{2}-2A+I)Bu_{ t-3-i}.$ $$

Let $\alpha_{1},\dots,\alpha_{d_{A}}$ denote the eigenvalues of $A$. We observe the following equality:

$$ $\displaystyle\sum_{i=0}^{t-3}CA^{i}(A^{2}-2A+I)Bu_{t-3-i}$ $\displaystyle=\sum_{i=0}^{t-3}C\sum_{n=1}^{d_{A}}\alpha_{n}^{i}(\alpha_{n}-1)^ {2}e_{n}e_{n}^{\top}Bu_{t-3-i}$ $\displaystyle=\sum_{n=1}^{d_{A}}\left(Ce_{n}e_{n}^{\top}B\right)\sum_{i=0}^{t- 3}\alpha_{n}^{i}(\alpha_{n}-1)^{2}u_{t-3-i}$ $\displaystyle=\sum_{n=1}^{d_{A}}\left(C_{n}B_{n}^{\top}\right)u_{(t-3):0} \tilde{\mu}_{\alpha_{n}}.$ $$

Observe that

$$ $\sum_{i=1}^{T-2}\tilde{\phi}_{i}\tilde{\phi}_{i}^{\top}=I.$ $$

Using this we have,

$$ $\displaystyle\sum_{i=0}^{t-3}CA^{i}(A^{2}-2A+I)Bu_{t-3-i}$ $\displaystyle=\sum_{n=1}^{d_{A}}\left(C_{n}B_{n}^{\top}\right)u_{(t-3):0} \tilde{\mu}_{\alpha_{n}}$ $\displaystyle=\sum_{n=1}^{d_{A}}\left(C_{n}B_{n}^{\top}\right)u_{(t-3):0}\left (\sum_{i=1}^{T-2}\tilde{\phi}_{i}\tilde{\phi}_{i}^{\top}\right)\tilde{\mu}_{ \alpha_{n}}$ $\displaystyle=\sum_{i=1}^{T-2}\left(\sum_{n=1}^{d_{A}}\tilde{\phi}_{i}^{\top} \tilde{\mu}_{\alpha_{n}}\left(C_{n}B_{n}^{\top}\right)\right)u_{(t-3):0}\tilde {\phi}_{i}$ $\displaystyle=\sum_{\ell=3}^{T}M^{\textrm{true}}_{\ell}u_{(t-1):0}v_{\ell}.$ $$

Therefore we have established $(2)$. Next we aim to prove $(3)$. We consider

$$ $\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{(t-1):0}v_{i}\|.$ $$

Combining Lemma 19 and Lemma 20 gives us that there is some constant $c^{\prime}$ such that,

$$ $\max_{\alpha\in[0,1]}|\tilde{\phi}_{i}^{\top}\tilde{\mu}_{\alpha}|~{}\leq~{}c^ {\prime}\exp(-i/4\log(T)).$ $$

So,

$$ $\displaystyle\|M^{\textrm{true}}_{i}u_{(t-1):0}v_{i}\|$ $\displaystyle=\|\sum_{n=1}^{d_{A}}\sigma_{i-1}^{-1/4}\tilde{\phi}_{i-i}^{\top} \tilde{\mu}_{\alpha_{n}}(C_{n}B_{n}^{\top})u_{(t-1):0}\left(\sigma_{i-1}^{1/4} \tilde{\phi}_{i-1}\right)\|$ $\displaystyle=\|\sum_{n=1}^{d_{A}}\tilde{\phi}_{i-i}^{\top}\tilde{\mu}_{\alpha _{n}}(C_{n}B_{n}^{\top})u_{(t-2):0}\tilde{\phi}_{i-1}\|$ $\displaystyle~{}\leq~{}d_{A}\exp(-(i-1)/4\log(T))\|C_{n}B_{n}^{\top}\|\|\phi_{ i-1}\|_{1}$ $\displaystyle~{}\leq~{}c^{\prime}d_{A}\sqrt{T}\exp(-(i-1)/4\log(T))\|C\|\|B\|.$ $$

Therefore,

$$ $\displaystyle\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{(t-1):0}v_{i}\|$ $\displaystyle~{}\leq~{}c^{\prime}d_{A}T^{3/2}\exp(-i/4\log(T))\|C\|\|B\|.$ $$

Therefore as long as

$$ $k~{}\geq~{}4\log(T)\log\left(\frac{T^{3/2}c^{\prime}d_{A}\|C\|\|B\|}{\epsilon} \right),$ $$

then

$$ $\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{(t-1):0}v_{i}\|~{}\leq~{}\frac{ \epsilon}{T}.$ $$

To prove $(4)$ we note that the statement is obvious for $i~{}\leq~{}2$. For $i~{}\geq~{}3$ the proof from Lemma D.1 of Hazan et al. () directly applies due to Lemma 19. Next, Lemma 21 proves $(5)$. Finally we prove $(6)$. Next, Lemma 21 proves $(5)$. Finally we prove $(6)$. Since we have $h(\alpha)=(\alpha-1)^{2}$ and $\ell=2$,

$$ $\displaystyle\max_{\alpha(A)}\left\{|h(\alpha)\alpha^{L-3}(1-\alpha^{T-L+1})(1 -\alpha)^{-1}|\right\}$ $\displaystyle=\max_{\alpha(A)}\left\{(1-\alpha)\alpha^{L-3}(1-\alpha^{T-L+1}) \right\}.$ (13) $$

To bound Eq. 13, consider the case where $\alpha$ is bounded away from $1$. Suppose $\alpha=1-\delta$, then

$$ $\displaystyle(1-\delta)^{L-3}~{}\leq~{}\frac{1}{T^{p}}\iff\log\left(\frac{1}{1 -\delta}\right)~{}\geq~{}\frac{p\log(T)}{L-3}.$ $$

Observe that for $\delta\in[0,1]$, $\log(1/(1-\delta))~{}\geq~{}\delta/2$. Therefore, if

$$ $\displaystyle\delta~{}\geq~{}\frac{2p\log(T)}{L-3},$ $$

we are guaranteed that $\alpha^{L-3}~{}\leq~{}1/T^{p}$. Next consider when $\alpha$ is very close to $1$. To ensure that Eq. 15 is bounded by $1/T^{p}$ we only require

$$ $\alpha~{}\geq~{}1-\frac{1}{T^{p}}.$ $$

Plugging in $p=1/4$, we conclude that Eq. 15 is bounded by $T^{-1/4}$ if

$$ $\alpha_{n}\in\left[0,1-\frac{\log(T)}{2(L-3)}\right]\cup\left[1-\frac{1}{T^{1/ 4}},1\right]\textrm{ for all }n\in[d_{A}].$ $$

∎

###### Proof of Theorem 7 .

###### Lemma 18 (Length Generalization Using Two Autoregressive Components) .

###### Proof.

### C.1 Properties of the Hankel Matrix for Two Autoregressive Terms

In Algorithm 2 we define

$$ $\tilde{\mu}_{\alpha}\stackrel{{\scriptstyle\text{def}}}{{=}}(\alpha-1)^{2} \begin{bmatrix}1&\alpha&\dots&\alpha^{T}\end{bmatrix}^{\top}\in\mathbb{R}^{T}$ $$

and

$$ $N_{T}=\int_{\alpha\in[0,1]}\tilde{\mu}_{\alpha}\tilde{\mu}_{\alpha}^{\top}d\alpha.$ $$

In what follows we present and prove several lemmas needed for the proof of Theorem 7.

###### Lemma 19 (Properties of $N_{T}$ ) .

For any $\alpha\in[0,1]$ and $1~{}\leq~{}i~{}\leq~{}T$,

$$ $\max_{\alpha\in[0,1]}|\phi_{i}^{\top}\tilde{\mu}_{\alpha}|~{}\leq~{}6^{1/4} \sigma_{i}^{1/4}.$ $$

###### Proof.

We have

$$ $\displaystyle\int_{\alpha\in[0,1]}\left(\phi_{i}^{\top}\tilde{\mu}_{\alpha} \right)^{2}d\alpha$ $\displaystyle=\phi_{i}^{\top}\left(\int_{\alpha\in[0,1]}\tilde{\mu}_{\alpha} \tilde{\mu}_{\alpha}^{\top}d\alpha\right)\phi_{i}$ $\displaystyle=\phi_{i}^{\top}N_{T}\phi_{i}=\sigma_{i}.$ $$

Next we observe that for $f_{w}(\alpha)\stackrel{{\scriptstyle\text{def}}}{{=}}\left(w^{\top}\tilde{\mu}
_{\alpha}\right)^{2}$, where $w$ is any unit-norm vector, we have that $f_{w}$ is $6$-Lipschitz on $[0,1]$. Indeed,

$$ $\displaystyle f_{w}^{\prime}(\alpha)$ $\displaystyle=\frac{d}{d\alpha}(\alpha-1)^{4}\left(\sum_{i=1}^{T}w_{i}\alpha^{ i-1}\right)^{2}$ $\displaystyle=2(\alpha-1)^{4}\left(\sum_{i=1}^{T}w_{i}\alpha^{i-1}\right)\left (\sum_{i=2}^{T}(i-1)w_{i}\alpha^{i-2}\right)+4\left(\sum_{i=1}^{T}w_{i}\alpha^ {i-1}\right)^{2}(\alpha-1)^{3}$ $\displaystyle~{}\leq~{}2(\alpha-1)^{4}\left(\frac{1-\alpha^{T}}{1-\alpha} \right)\left(\sum_{i=1}^{T-1}i\alpha^{i-1}\right)+4\left(\frac{1-\alpha^{T}}{1 -\alpha}\right)^{2}(\alpha-1)^{3}$ $\displaystyle=2(\alpha-1)^{4}\left(\frac{1-\alpha^{T}}{1-\alpha}\right)\left( \frac{1-T\alpha^{T-1}+(T-1)\alpha^{T}}{(1-\alpha)^{2}}\right)+4\left(\frac{1- \alpha^{T}}{1-\alpha}\right)^{2}(\alpha-1)^{3}$ $\displaystyle=2\left(1-\alpha^{T}\right)\left(1-T\alpha^{T-1}+(T-1)\alpha^{T} \right)+4\left(1-\alpha^{T}\right)^{2}(\alpha-1)$ $\displaystyle~{}\leq~{}2+4=6.$ $$

Consider any non-negative L-Lipschitz function $f$ that reaches some maximum value $g_{\textrm{max}}$ over $[0,1]$. The function $f$ which satisfies $L$-Lipschitzness, attains $g_{\textrm{max}}(f)$ and also has minimum possible area $A(f)\stackrel{{\scriptstyle\text{def}}}{{=}}\int_{\alpha\in[0,1]}f(\alpha)d\alpha$ is

$$ $\displaystyle f^{*}(\alpha)$ $\displaystyle=\begin{cases}L\alpha,&\textrm{ for }\alpha\in[0,\alpha^{*}]\\ \max\left\{g_{\textrm{max}}-L(\alpha-\alpha^{*}),0\right\},&\textrm{ for } \alpha\in[\alpha^{*},1]\end{cases}$ $\displaystyle=\begin{cases}L\alpha,&\textrm{ for }\alpha\in[0,\alpha^{*}]\\ g_{\textrm{max}}-L(\alpha-\alpha^{*}),&\textrm{ for }\alpha\in[\alpha^{*}, \alpha^{*}+\frac{g_{\textrm{max}}}{L}]\\ 0,&\textrm{ for }\alpha\in[\alpha^{*}+\frac{g_{\textrm{max}}}{L},1]\end{cases}.$ $$

Indeed, any oscillation away from this piecewise linear function would either increase the total area or violate the Lipschitz constraint. For this to be a valid construction we must have $L\alpha^{*}=g_{\textrm{max}}$ and therefore the minimum corresponding area is

$$ $A(f^{*})=\int_{\alpha\in[0,1]}f^{*}(\alpha)d\alpha=\frac{1}{2}(\alpha^{*})(L \alpha^{*})+\frac{1}{2}(g_{\textrm{max}}/L)g_{\textrm{max}}=\frac{g_{\textrm{ max}}^{2}}{L}.$ $$

And therefore for any function $f$ we have $g_{\textrm{max}}(f)~{}\leq~{}\sqrt{LA(f)}$. Using this for $f_{\phi_{i}}(\alpha)$ we have

$$ $\max_{\alpha\in[0,1]}f_{\phi_{i}}(\alpha)=\max_{\alpha\in[0,1]}(\phi_{i}^{\top }\tilde{\mu}_{\alpha})^{2}~{}\leq~{}\sqrt{6\int_{\alpha\in[0,1]}\left(\phi_{i} ^{\top}\tilde{\mu}_{\alpha}\right)^{2}d\alpha}=\sqrt{6\sigma_{i}}.$ $$

We conclude by noting

$$ $\max_{\alpha\in[0,1]}|\phi_{i}^{\top}\tilde{\mu}_{\alpha}|=\sqrt{\max_{\alpha \in[0,1]}(\phi_{i}^{\top}\tilde{\mu}_{\alpha})^{2}}~{}\leq~{}6^{1/4}\sigma_{i} ^{1/4}.$ $$

∎

###### Lemma 20 (Adapted from Lemma $E.2$ from Hazan et al. ( 2017b ) ) .

Let $\sigma_{j}$ be the $j$-th top singular value of $N_{T}$. Then for all $T~{}\geq~{}10$ we have

$$ $\sigma_{j}~{}\leq~{}\min\left(\frac{3}{2},K\cdot c^{-j/\log(T)}\right),$ $$

where $c=e^{\pi^{2}/4}\approx 11.79$ and $K~{}\leq~{}10^{6}$ is an absolute constant.

###### Proof.

The proof provided in Hazan et al. () applies directly to $N_{T}$ with only one necessary modification to bound the trace. Observe that
we have

$$ $\displaystyle(N_{T})_{ij}$ $\displaystyle=\int_{\alpha\in[0,1]}(\alpha-1)^{4}\alpha^{i+j-2}d\alpha$ $\displaystyle=\int_{\alpha\in[0,1]}\alpha^{i+j}-2\alpha^{i+j-1}+\alpha^{i+j-2}d\alpha$ $\displaystyle=\frac{24}{(i+j-1)(i+j)(i+j+1)(i+j+2)(i+j+3)}.$ $$

Therefore,

$$ $\sigma_{j}~{}\leq~{}\mathrm{tr}(N_{T})=\sum_{i=1}^{T}\frac{24}{(2i-1)(2i)(2i+1 )(2i+2)(2i+3)}~{}\leq~{}\sum_{i=1}^{T}\frac{24}{(2i)^{5}}=\frac{3}{4}\sum_{i=1 }^{T}\frac{1}{i^{5}}<\frac{3}{2}.$ $$

The remainder of the proof is an exact copy of the proof of Lemma $E.2$ with $3/4$ replaced by $3/2$.
∎

###### Lemma 21 (Controlling the $\ell_{1}$ norm of the filters) .

Let $(\sigma_{j},\phi_{j})$ be the $j$-th largest eigenvalue-eigenvector pair of $N_{T}$. Then for $T~{}\geq~{}4$,

$$ $\|\phi_{j}\|_{1}~{}\leq~{}O\left(\frac{\log T}{\sigma_{j}^{1/4}}\right).$ $$

###### Proof.

This proof is a copy from the proof of Lemma E.5 in Hazan et al. () with only one noted modification. We note that $E$ as defined in their proof is entrywise bounded (for $T~{}\geq~{}4$) by $24/T^{5}~{}\leq~{}2/T^{3}$ (which is the stated bound they use for their matrix of interest). We also must show the base case is true for $T_{0}=4$ instead of $T_{0}=2$. We have

$$ $\displaystyle\|N_{4}^{1/4}\|_{2\to 1}=\sup_{x:\|x\|_{2}~{}\leq~{}1}\|N_{4}^{1/ 4}x\|_{1}~{}\leq~{}\sum_{i,j=1}^{4}|\left(N_{4}^{1/4}\right)_{ij}|<2.$ $$

We note that a tighter result is actually true for $N_{T}$ in that $\|\phi_{j}\|_{1}~{}\leq~{}O\left(\frac{\log T}{\sigma_{j}^{1/8}}\right)$. However, we omit this statement and proof because we don’t leverage it for a tighter result overall.

∎

In Algorithm 2 we define

$$ $\tilde{\mu}_{\alpha}\stackrel{{\scriptstyle\text{def}}}{{=}}(\alpha-1)^{2} \begin{bmatrix}1&\alpha&\dots&\alpha^{T}\end{bmatrix}^{\top}\in\mathbb{R}^{T}$ $$

and

$$ $N_{T}=\int_{\alpha\in[0,1]}\tilde{\mu}_{\alpha}\tilde{\mu}_{\alpha}^{\top}d\alpha.$ $$

We have

$$ $\displaystyle(N_{T})_{ij}$ $\displaystyle=\int_{\alpha\in[0,1]}(\alpha-1)^{4}\alpha^{i+j-2}d\alpha$ $\displaystyle=\int_{\alpha\in[0,1]}\alpha^{i+j}-2\alpha^{i+j-1}+\alpha^{i+j-2}d\alpha$ $\displaystyle=\frac{24}{(i+j-1)(i+j)(i+j+1)(i+j+2)(i+j+3)}.$ $$

###### Lemma 19 (Properties of N T subscript 𝑁 𝑇 N_{T} italic_N start_POSTSUBSCRIPT italic_T end_POSTSUBSCRIPT ) .

###### Proof.

###### Lemma 20 (Adapted from Lemma E ⁢ .2 𝐸 .2 E.2 italic_E .2 from Hazan et al. ( 2017b ) ) .

###### Proof.

###### Lemma 21 (Controlling the ℓ 1 subscript ℓ 1 \ell_{1} roman_ℓ start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT norm of the filters) .

###### Proof.

## Appendix D Proof for Length Generalization via Tensorized Spectral Filtering

The proof of Theorem 10 ultimately comes from Theorem 11 and its proof in Appendix A. Theorem 11 abstracts the necessary assumptions needed to obtain a length generalization guarantee. In Lemma 22 we prove that Algorithm 3 satisfies these assumptions.

###### Proof of Theorem 7 .

By Lemma 22 and the assumptions made in the statement of Theorem 10, we may apply Theorem 11 to Algorithm 3 to get that

$$ $\sum_{t=1}^{T}\ell_{t}(M^{t},L)-\min_{M^{*}\in\mathcal{K}_{\|C\|\|B\|}}\sum_{t =1}^{T}\ell_{t}(M^{*},T)~{}\leq~{}\left(12k^{3/2}\|C\|^{2}\|B\|^{2}\log^{2}(T) +8\|C\|^{2}\|B\|^{2}\right)\sqrt{T}.$ $$

∎

###### Lemma 22 (Length Generalization for Tensorized Spectral Filtering) .

Recall that in Algorithm 3 we let $T^{\prime}=\left(\lceil\sqrt{T-2}\rceil\right)^{2}+2$ and $\phi_{1},\dots,\phi_{\sqrt{T^{\prime}-2}}$ be the orthonormal eigenvectors of $H_{\sqrt{T^{\prime}-2}}$ with eigenvalues $\sigma_{1},\dots,\sigma_{\sqrt{T^{\prime}-2}}$.
Algorithm 3 is equivalent to Algorithm 4 with the following:

- (a)
$p_{t}(y_{t-1:1})=2y_{t-1}-y_{t-2}$
- (b)
$v_{1}=e_{1}$, $v_{2}=e_{2}$ and for $i,j~{}\geq~{}1$,
$v_{i+k(j-1)+2}=(0,0,\sigma_{i}^{1/4}\phi_{i}\otimes\sigma_{j}^{1/4}\phi_{j}).$

Define $M^{\textrm{true}}$ as follows:

$$ $M^{\textrm{true}}_{1}\stackrel{{\scriptstyle\text{def}}}{{=}}CB,$ $$

$$ $M^{\textrm{true}}_{2}\stackrel{{\scriptstyle\text{def}}}{{=}}C(A-2I)B,$ $$

and for $i,j~{}\geq~{}1$,

$$ $M^{\textrm{true}}_{i+k(j-1)+2}\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{n= 1}^{d_{A}}\frac{1-\alpha_{n}}{1-\alpha_{n}^{\sqrt{T}}}\left(\sigma_{i}^{-1/4} \phi_{i}^{\top}\mu_{\alpha_{n}}\right)\left(\sigma_{j}^{-1/4}\phi_{j}^{\top} \mu_{\alpha_{n}^{\sqrt{T}}}\right)(C_{n}B_{n}^{\top}).$ $$

Then the following properties hold

- 1.
For $h(A)=(A-I)^{2}$ and $\ell_{1}=2$
$y_{t}-p_{t}(y_{t-1:1})=\sum_{i=1}^{\ell_{1}}M^{\textrm{true}}_{i}u_{t-i}+\sum_
{i=1}^{t-\ell_{1}}CA^{i}h(A)Bu_{t-\ell_{1}-i}.$
- 2.
$y_{t}-p_{t}(y_{t-1:1})=\sum_{i=1}^{T}M^{\textrm{true}}_{i}u_{t-1:1}v_{i}$.
- 3.
For $k=\Omega\left(\log(T)\cdot\log\left(d_{A}T\|C\|\|B\|/\epsilon\right)\right)$,
$\|\sum_{i=k+1}^{T}M^{\textrm{true}}_{i}u_{t-1:1}v_{i}\|~{}\leq~{}\epsilon/T.$
- 4.
For any $i\in[T]$
$\|M^{\textrm{true}}_{i}\|~{}\leq~{}\|C\|\|B\|.$
- 5.
For any $i\in[T]$, $\|v_{i}\|_{1}~{}\leq~{}\log^{3}(T)$ and $\{v_{i}\}_{i\in[T]}$ are orthonormal.
- 6.
Finally if the spectrum of $A$ lies in the interval
$\left[0,1-\frac{\log(T)}{2(L-2)}\right]\cup\left[1-\frac{1}{2T^{1/4}},1\right],$
then
$\max_{\alpha(A)}\left\{|h(\alpha)\alpha^{L-\ell_{1}-1}(1-\alpha^{T-L+1})(1-
\alpha)^{-1}|\right\}~{}\leq~{}\frac{1}{T^{1/4}}.$

###### Proof of Lemma 22 .

Suppose $y_{t}$ evolves as an LDS. By definition, there exist matrices $(A,B,C)$ such that

$$ $y_{t}=\sum_{i=1}^{t}CA^{i-1}Bu_{t-i}.$ (14) $$

Assume w.l.o.g. that $A$ is diagonal (otherwise replace $C$ with $CP$ and $B$ with $P^{-1}B$ where $P$ diagonalizes $A$). Observe that $(1)$ is true since unraveling Eq. 14 gives

$$ $\displaystyle y_{t}-2y_{t-1}+y_{t-2}$ $\displaystyle=CBu_{t-1}+C(A-2I)Bu_{t-2}+\sum_{i=0}^{t-3}CA^{i}(A^{2}-2A+I)Bu_{ t-3-i}.$ $$

Let

$$ $\tilde{\mu}_{\alpha}^{T}\stackrel{{\scriptstyle\text{def}}}{{=}}(1-\alpha)^{2} [1,\alpha,\alpha^{2},\dots,\alpha^{T-1}],$ $$

and let

$$ $\mu_{\alpha}^{T}\stackrel{{\scriptstyle\text{def}}}{{=}}(1-\alpha)[1,\alpha, \alpha^{2},\dots,\alpha^{T-1}].$ $$

Observe that when $T$ is a perfect square,

$$ $\tilde{\mu}_{\alpha}^{T}=\frac{1-\alpha}{1-\alpha^{\sqrt{T}}}\mu_{\alpha}^{ \sqrt{T}}\otimes\mu_{\alpha^{\sqrt{T}}}^{\sqrt{T}}.$ $$

Let $\alpha_{1},\dots,\alpha_{d_{A}}$ denote the eigenvalues of $A$. Recall we set $T^{\prime}=\left(\lceil\sqrt{T-2}\rceil\right)^{2}+2$ so that $\sqrt{T^{\prime}-2}$ is an integer. We observe the following equality:

$$ $\displaystyle\sum_{i=0}^{t-3}CA^{i}(A^{2}-2A+I)Bu_{t-3-i}$ $\displaystyle=\sum_{i=0}^{t-3}C\sum_{n=1}^{d_{A}}\alpha_{n}^{i}(\alpha_{n}-1)^ {2}e_{n}e_{n}^{\top}Bu_{t-3-i}$ $\displaystyle=\sum_{n=1}^{d_{A}}\left(Ce_{n}e_{n}^{\top}B\right)\sum_{i=0}^{t- 3}\alpha_{n}^{i}(\alpha_{n}-1)^{2}u_{t-3-i}$ $\displaystyle=\sum_{n=1}^{d_{A}}\left(C_{n}B_{n}^{\top}\right)u_{(t-3):0} \tilde{\mu}_{\alpha_{n}}^{T^{\prime}-2}$ $\displaystyle=\sum_{n=1}^{d_{A}}\frac{1-\alpha_{n}}{1-\alpha_{n}^{\sqrt{T^{ \prime}-2}}}\left(C_{n}B_{n}^{\top}\right)u_{(t-3):0}\left(\mu_{\alpha_{n}}^{ \sqrt{T^{\prime}-2}}\otimes\mu_{\alpha_{n}^{\sqrt{T^{\prime}-2}}}^{\sqrt{T^{ \prime}-2}}\right).$ $$

Recall that $\left\{\phi_{i}\right\}$ are the orthonormal eigenvectors of the Hankel matrix $H_{\sqrt{T^{\prime}-2}}$. Observe that $\left\{\phi_{i}\otimes\phi_{j}\right\}$ is an orthonormal set, inheriting this property from $\left\{\phi_{i}\right\}$. Therefore,

$$ $\displaystyle u_{(t-3):0}\left(\mu_{\alpha_{n}}\otimes\mu_{\alpha_{n}^{\sqrt{T ^{\prime}-2}}}\right)$ $\displaystyle=u_{(t-3):0}\left(\sum_{i,j=1}^{\sqrt{T^{\prime}-2}}(\phi_{i} \otimes\phi_{j})(\phi_{i}\otimes\phi_{j})^{\top}\right)\left(\mu_{\alpha_{n}} \otimes\mu_{\alpha_{n}^{\sqrt{T^{\prime}-2}}}\right)$ $\displaystyle=\sum_{i,j=1}^{\sqrt{T^{\prime}-2}}\phi_{i}^{\top}\mu_{\alpha_{n} }\phi_{j}^{\top}\mu_{\alpha_{n}^{\sqrt{T^{\prime}-2}}}u_{(t-3):0}(\phi_{i} \otimes\phi_{j})$ $$

Therefore, letting

$$ $M_{ij}\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{n=1}^{d_{A}}\frac{1-\alpha _{n}}{1-\alpha_{n}^{\sqrt{T^{\prime}-2}}}\phi_{i}^{\top}\mu_{\alpha_{n}}\phi_{ j}^{\top}\mu_{\alpha_{n}^{\sqrt{T^{\prime}-2}}}\left(C_{n}B_{n}^{\top}\right),$ $$

$$ $\displaystyle\sum_{n=1}^{d_{A}}\frac{1-\alpha_{n}}{1-\alpha_{n}^{\sqrt{T^{ \prime}-2}}}\left(C_{n}B_{n}^{\top}\right)u_{(t-3):0}\left(\mu_{\alpha_{n}} \otimes\mu_{\alpha_{n}^{\sqrt{T^{\prime}-2}}}\right)$ $\displaystyle=\sum_{i,j=1}^{\sqrt{T^{\prime}-2}}M_{ij}u_{(t-3):0}(\phi_{i} \otimes\phi_{j})$ $\displaystyle=\sum_{i,j=1}^{\sqrt{T^{\prime}-2}}M^{\textrm{true}}_{i+k(j-1)+2} u_{(t-3):0}(\sigma_{i}^{-1/4}\phi_{i}\otimes\sigma_{j}^{-1/4}\phi_{j})$ $\displaystyle=\sum_{\ell=3}^{T}M^{\textrm{true}}_{\ell}u_{(t-1):1}v_{\ell}.$ $$

This concludes the proof of $(2)$. To prove $(3)$ we use Lemma 13.4 in Hazan & Singh (): there is some universal constant $c^{\prime}$ such that,

$$ $\max_{\alpha\in[0,1]}|\phi_{i}^{\top}\mu_{\alpha}|~{}\leq~{}c^{\prime}(\sqrt{T ^{\prime}-2})^{2}\exp(-i/\log(\sqrt{T^{\prime}-2}))=c^{\prime}T\exp(-2i/\log(T )).$ $$

Suppose

$$ $k~{}\geq~{}\frac{1}{2}\log(T)\cdot\log\left(c^{\prime}d_{A}T^{7/2}\|C\|\|B\|/ \epsilon\right)$ $$

Let $\ell=i+k(j-1)+2$ and suppose either $i~{}\geq~{}k$ or $j~{}\geq~{}k$ (and therefore $\ell~{}\geq~{}k+2$). Then, using that for $T>3$, $\max_{\alpha\in[0,1]}(1-\alpha)/(1-\alpha^{\sqrt{T^{\prime}-2}})~{}\leq~{}1$,

$$ $\displaystyle\|M^{\textrm{true}}_{\ell}u_{(t-1):0}v_{\ell}\|$ $\displaystyle=\|\sum_{n=1}^{d_{A}}\frac{1-\alpha_{n}}{1-\alpha_{n}^{\sqrt{T}}} \left(\sigma_{i}^{-1/4}\phi_{i}^{\top}\mu_{\alpha_{n}}\right)\left(\sigma_{j}^ {-1/4}\phi_{j}^{\top}\mu_{\alpha_{n}^{\sqrt{T}}}\right)(C_{n}B_{n}^{\top})u_{( t-3):0}\left(\sigma_{i}^{1/4}\phi_{i}\otimes\sigma_{j}^{1/4}\phi_{j}\right)\|$ $\displaystyle~{}\leq~{}d_{A}\left(c^{\prime}(T^{\prime}-2)\exp(-2k/\log(T^{ \prime}-2))\right)\|C\|\|B\|\|u_{(t-3):0}\|_{\infty}\|\phi_{i}\otimes\phi_{j} \|_{1}$ $\displaystyle~{}\leq~{}c^{\prime}d_{A}T^{3/2}\exp(-2k/\log(T))\|C\|\|B\|$ $\displaystyle~{}\leq~{}\epsilon/T^{2}.$ $$

Therefore,

$$ $\displaystyle\|\sum_{\ell=k+2}^{T^{\prime}-2}M^{\textrm{true}}_{\ell}u_{(t-1): 1}v_{\ell}\|~{}\leq~{}\epsilon/T.$ $$

The proof of $(4)$ comes from Lemma D.1 of Hazan et al. (). The proof extends directly to

$$ $M^{\textrm{true}}_{ij}\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{n=1}^{d_{A }}\frac{1-\alpha}{1-\alpha^{\sqrt{T^{\prime}-2}}}\phi_{i}^{\top}\mu_{\alpha_{n }}\phi_{j}^{\top}\mu_{\alpha_{n}^{L}}(C_{n}B_{n}^{\top}),$ $$

since it proceeds by bounding $\max_{i\in[k]}\max_{\alpha\in[0,1]}\phi_{i}^{\top}\mu_{\alpha}$ by Lemma E.4. To prove $(5)$ we use Lemma 17 from Hazan et al. ().

Therefore for $v_{3},\dots,v_{T}$ we have for some universal constant $c>0$,

$$ $\displaystyle\|v_{i+k(j-1)+2}\|_{1}$ $\displaystyle=\|\sigma_{i}^{1/4}\phi_{i}\otimes\sigma_{j}^{1/4}\phi_{j}\|_{1}$ $\displaystyle~{}\leq~{}\sigma_{i}^{1/4}\sigma_{j}^{1/4}\|\phi_{i}\|_{1}\|\phi_ {j}\|_{1}$ $\displaystyle~{}\leq~{}c\log^{2}(T)$ $\displaystyle~{}\leq~{}\log^{3}(T),$ $$

where the last inequality holds for $T$ large enough.
Finally we prove $(6)$. Since we have $h(\alpha)=(\alpha-1)^{2}$ and $\ell=2$,

$$ $\displaystyle\max_{\alpha(A)}\left\{|h(\alpha)\alpha^{L-3}(1-\alpha^{T-L+1})(1 -\alpha)^{-1}|\right\}$ $\displaystyle=\max_{\alpha(A)}\left\{(1-\alpha)\alpha^{L-3}(1-\alpha^{T-L+1}) \right\}.$ (15) $$

To bound Eq. 15, consider the case where $\alpha$ is bounded away from $1$. Suppose $\alpha=1-\delta$, then

$$ $\displaystyle(1-\delta)^{L-3}~{}\leq~{}\frac{1}{T^{p}}\iff\log\left(\frac{1}{1 -\delta}\right)~{}\geq~{}\frac{p\log(T)}{L-3}.$ $$

Observe that for $\delta\in[0,1]$, $\log(1/(1-\delta))~{}\geq~{}\delta/2$. Therefore, if

$$ $\displaystyle\delta~{}\geq~{}\frac{2p\log(T)}{L-3},$ $$

we are guaranteed that $\alpha^{L-3}~{}\leq~{}1/T^{p}$. Next consider when $\alpha$ is very close to $1$. To ensure that Eq. 15 is bounded by $1/T^{p}$ we only require

$$ $\alpha~{}\geq~{}1-\frac{1}{T^{p}}.$ $$

Plugging in $p=1/4$, we conclude that Eq. 15 is bounded by $T^{-1/4}$ if

$$ $\alpha_{n}\in\left[0,1-\frac{\log(T)}{2(L-3)}\right]\cup\left[1-\frac{1}{T^{1/ 4}},1\right]\textrm{ for all }n\in[d_{A}].$ $$

∎

###### Proof of Theorem 7 .

###### Lemma 22 (Length Generalization for Tensorized Spectral Filtering) .

###### Proof of Lemma 22 .

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: - Why do we necessarily care about competing with the best LDS predictor? 
One receives the input/features before predicting, making it possible to 
make "improper" predictions. For instance, the Vovk-Azoury-Warmuth forecaster 
guarantees logarithmic static regret without any assumptions on the data 
by leveraging improper predictions. Analogously, it could be the case that 
the best LDS predictor is much worse than the best improper predictor.

- I don't understand how the problematic eigenvalues of A are non-extremal ones; what
exactly is special about the upper and lower bounds, that causes problems 
in the range between them?
soundness: 2
strengths: - The study of context length generalization is interesting and has a lot 
of practical relevance, especially given the recent surge of interest in 
transformer architectures. 
- The paper is generally well-written and easy to follow
summary: The paper considers the problem of sequence prediction of linear dynamical systems, and studies 
whether it is necessary to remember the entire history of inputs 
to predict optimally. To this end, the paper introduces the notion of asymmetric regret, which 
is the regret of the learner compared with a comparator which uses a longer context than the 
learner. It is shown that the class of spectral filtering algorithms can guarantee $\sqrt{T}$
asymmetric regret, under suitable assumptions, demonstrating that these existing algorithms can 
achieve non-trivial context-length generalization with no modification
weaknesses: - The asymmetric regret seems to be a *weaker* notion than usual regret; often regret guarantees 
hold for an *arbitrary* comparator, which would include comparators that utilize more information 
than the learner as a special case. Yet 
it is claimed on lines 258/259 that "The comparator can observe more information. Thus, this is a stronger, more difficult guarantee to obtain than classical regret."

- The experimental results in figure 5 seem flawed; the shaded regions 
imply that the models can reach accuracy above 100%. I assume the 
shaded region must be $\pm$ some measure of spread (unspecified), 
but this doesn't make sense when it extends outside the domain of the 
measurement.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: 1. Can the authors present some intuition as to the assumption on the spectrum that is required in the main theorem?  The precise union of intervals seems extremely unmotivated to me.  While I understand that it is qualitatively reasonable in the sense that as the amount of data becomes smaller, the assumption becomes stricter, I do not have a lot of intuition beyond that.

2. While I realize that the authors present some empirical evidence suggesting that the main theorem's spectral assumption is necessary, can they provide any theoretical lower bounds for their algorithm?

3. How can the accuracy in Figure 5 be greater than 1?
soundness: 2
strengths: This paper sets out to study length generalization and proposes a new definition that formalizes the concept, at least in the task of sequential prediction.  Furthermore, they demonstrate that in the context of noiseless LDS', a natural algorithm based on earlier work in linear control succeeds in length generalization according to their proposed definition.  The proofs are correct as written and clearly presented.
summary: This paper studies length generalization in linear dynamical systems from the perspective of spectral filtering.  Length generalization, the phenomenon by which models trained to conduct algorithmic tasks on short sequences can then accurately apply the same algorithmic principles to longer inputs, has seen much recent interest in language models.  The authors examine a similar problem in the context of noiseless LDSs, where they define length generalization though a new notion of regret they call Asymmetric Regret that allows the comparator policy to incorporate a longer history than the learner can.  The authors leverage recent results on spectral filtering to demonstrate that some marginally stable linear systems can be learned (in the sense of Asymmetric Regret) using a natural online empirical risk minimization algorithm defined by small Frobenius norm linear functions on a basis given by spectral filters.  The authors then demonstrate that this algorithm attains good Asymmetric Regret as long as the spectrum of the eigenvalues of the system matrix A satisfies a certain technical assumption.  Finally, the authors conclude with two experiments: first showing that their assumption on the spectrum of A appears to be necessary by considering synthetic data from randomly generated LDS's and second showing that a certain neural architecture motivated by spectral filtering appears to length generalize when considering induction heads.
weaknesses: I think the work has several major weaknesses:

1. The authors claim their study is motivated by the challenge of length generalization in LLMs, but they did not spend sufficient time justifying the connection between this motivation and their actual results.  I will discuss the empirical aspects below, but on the level of theory, it is not completely clear to me to what extent the study of online prediction in LDS's provides intuition for LLMs.  I think one way of connecting these two disparate concerns would be to note that because LLMs are trained with next token prediction, one may think of generation as an online prediction problem and thus Asymmetric Regret is a natural target notion as the LM is trained to produce algorithms with good `symmetric regret' on algorithmic tasks of interest, but, in order to length-generalize in a meaningful sense, small asymmetric regret (with respect to the longer sequence) is necessary.  If this is the way the authors are thinking about it, it would be helpful if they were to spell this out.  Assuming that this is correct, I guess I am a little confused as to what this means for length generalization in the context of LLMS?  It is not at all obvious to me that the theoretical results necessarily suggest that the Spectral Transform Unit of Agarwal et al 2023 is helpful in length generalization (at least beyond noiseless linear dynamical systems).  What broader intuition are we supposed to glean from the main theorem?

2. I think that the strength of the technical contribution may not quite meet the high bar set by the standards of the conference.  While it is nice that the authors introduce this notion of Asymmetric Regret, it is not entirely clear to what extent it is meaningful beyond the setting of LDS'.  Furthermore, on the level of proof techniques, as said in the paper, Lemma 5 is essentially standard.  Lemma 6 follows from elementary computations on top of earlier work by Hazan et al 2017 and standard results in the field of online control.  Finally, the main theorem is immediate from applying these two lemmata.  Thus, I am a little unclear as to the extent of the technical contribution beyond the introduction of the Asymmetric Regret.  Furthermore, it might be helpful for the authors to discuss alternative notions of regret from the online learning literature, as I think Asymmetric Regret can be thought of as a special case of the $\Phi$-regret introduced in Stolz and Lugosi 2007 and studied in *Online Learning: Beyond Regret* by Rakhlin, Sridharan, and Tewari 2011, where the $\Phi$ functions map a function class allowed to see the entire history to one constrained to seeing the most recent $T^q$ inputs.  

3. The main theorem rests on a fairly unmotivated assumption on the spectrum of a system matrix and there is no theory regarding whether or not this is necessary.

4.  While I am reviewing this paper primarily as a theoretical one, I do wish to mention that I am not entirely convinced by the experiments on the STU networks.  First, the results in Figure 5 appear extremely noisy.  Second, and more importantly, there is no comparison to comparable results with transformers.  My understanding of some recent empirical results in the length generalization literature, such as *What Algorithms can Transformers Learn? A Study in Length Generalization* by Zhou et al 2023, is that induction heads should be relatively easy for transformers to learn due to their ease of representation; why do we expect STUs to improve in this setting?

---

confidence: 2
contribution: 2
initial_rating: 3
presentation: 2
questions: 1.	Generalizability: Could the authors discuss how their approach might extend to more general settings, especially those where data does not conform strictly to LDS assumptions? 
2.	Handling “Bad” Eigenvalues: Theoretical and empirical results suggest that the approach struggles when eigenvalues fall within certain “bad” ranges. Could the authors elaborate on adjustments to handle such cases?
3.	Comparison with Full-Context Models: In practice, how closely do regret bounds from shorter context lengths compare to those obtained with full sequence contexts? Are the additional comparative metrics that are relevant here? 
4.	Empirical Testing Beyond Synthetic Data: This is needed to provide insights into the approach’s practical feasibility and generalizability.
5.	Alignment with Hazan’s Work: How does the adaptation of the Asymmetric-Regret metric aligns with or diverges from Hazan’s original work? A detailed and systematic discussion is needed to understand the key contributions of this work.
soundness: 2
strengths: 1.	The paper extends the Asymmetric-Regret framework by applying it to limited context settings in spectral filtering. This adaptation addresses the relatively unexplored problem of length generalization for sequence prediction with limited context.
2.	Algorithm 1 introduces a modification of spectral filtering using shorter context windows, providing a new approach to minimize regret relative to models using the full sequence.
summary: The paper presents a novel approach to length generalization in sequence prediction using an Asymmetric-Regret metric. This metric measures prediction performance for models constrained to shorter context lengths, compared to a benchmark with access to the full sequence history. The authors apply this metric within spectral filtering for linear dynamical systems (LDS) and introduce a gradient-based learning algorithm that maintains sublinear Asymmetric-Regret bounds, enabling generalization over long sequences even with limited training contexts. 
This work builds on foundational contributions by Hazan and colleagues, who developed algorithms for spectral filtering in LDS under online convex optimization frameworks. The authors extend Hazan’s ideas by focusing specifically on achieving Asymmetric-Regret bounds with shorter context lengths.
weaknesses: 1.	Strong Assumptions:The main result relies on restrictive assumptions about LDS structures and eigenvalue constraints (e.g., eigenvalues must fall within “good” ranges), which may limit the algorithm’s applicability in situations that do not strictly follow LDS dynamics or contain eigenvalues outside these ranges.

2.	Limited Empirical Validation: The empirical scope is narrow, with experiments focused primarily on synthetic LDS data and a single deep learning task. This raises concerns about the method’s practical utility and performance in diverse real-world settings.

3.	Conceptual Novelty and Integration of Existing Ideas: While the application of Asymmetric-Regret bounds to shorter contexts is novel, the overall contribution seems primarily integrative, synthesizing elements from Hazan’s work on spectral filtering, convex optimization, and regret minimization. The empirical and conceptual innovations feel incremental rather than groundbreaking, especially given the limited empirical exploration.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: 1. It seems your result holds only in the noiseless setting. What happens if noise is introduced? Does the regret bound of Hazan et al. (2017b) hold in this case as well?

2. What happens if we allow the predictor to compute a "sketch" of the history, rather than a hard truncation?
soundness: 3
strengths: In my opinion, the primary contribution of the paper is conceptual; it shows that meaningful regret bounds can still be achieved even when the predictor is not exposed to the full history, at least in the context of linear dynamic systems. This may inspire future work to extend this idea to other settings. As the authors point out, this truncated scenario is also inspired by the limited token-length prediction in LLMs (although this is not directly related to the current paper).
summary: This paper studies the problem of predicting the outputs of a linear dynamic system using only a truncated history. The paper shows that the regret of a predictor with history length $T^q$ is upper bounded by $\tilde{O}(\sqrt{T})$ compared to the full-length history (i.e., length $T$) experts, provided the data is noiseless and follows some underlying linear dynamic system. This is achieved at the cost of restricting the eigenvalue (depending on $q$) of the leading matrix $A$ of the linear dynamic system.
weaknesses: The proof idea appears to me to be quite simple, essentially involving the application of an online convex optimization predictor on the *truncated* expert. The regret bound follows from the fact that the performance of the optimal truncated expert is close to that of the optimal full-history predictor (using the assumption that the eigenvalues of $A$ are bounded). The final regret bound is essentially a restatement of Hazan et al. (2017b).

As I am not an expert in linear dynamic system theory, I cannot comment on the significance of relating truncated experts to full-history experts in that field. In particular, I am unsure how restrictive it is to constrain the eigenvalues of $A$.

From an online learning perspective, the technical contribution is minimal (both algorithmically and analytically), as the analysis closely follows Hazan et al. (2017b).

Meta-review: This paper studies length generalization in sequence prediction and defines a new metric of performance called asymmetric regret, which measures the regret compared with a predictor with longer context length than available to the learner. Under this new metric, the authors show that an algorithm based on spectral filtering attains good asymmetric regret under certain technical assumptions. Experiments results are presented to validate the theoretical findings. 

This is a borderline submission. The main weakness raised by the reviewers is the assumption on the spectrum of the system matrix. Although the authors later provided a new algorithm that might get rid of such assumption, another review cycle might be necessary to fully validate these new results. Another weakness raised by the reviewers is the technical novelty. Although the authors provided a summary of the novel parts of their proof, it is still unclear if the reviewers' concern has been addressed. 

Given all the factors mentioned above and the high standards of ICLR, I lean towards rejecting this submission.

Decision: Reject