Provable Length Generalization in Sequence Prediction via Spectral Filtering
Annie Marsden, Evan Dogariu, Naman Agarwal, Xinyi Chen, Daniel Suo, Elad Hazan · 2024
Read Provable Length Generalization in Sequence Prediction via Spectral Filtering by Annie Marsden, Evan Dogariu, Naman Agarwal, Xinyi Chen, Daniel Suo, Elad Hazan (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01035.txt.
Description
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.
Catalog record
| CREATOR | Annie Marsden, Evan Dogariu, Naman Agarwal, Xinyi Chen, Daniel Suo, Elad Hazan |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-01035
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Provable Length Generalization in Sequence Prediction via Spectral Filtering Annie Marsden, Evan Dogariu, Naman Agarwal, Xinyi Chen, Daniel Suo, Elad Hazan 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., 2017b ; Hazan et al., 2018 ) . 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., 2023 ) , a neural architecture built using spectral filtering, has recently shown promise on sequence prediction over a range of modalities ( Liu et al., 2024 ) . 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., 2023 ; Anil et al., 2022 ; Jelassi et al., 2023 ; Zhou et al., 2023 ; Delétang et al., 2022 ; Dziri et al., 2024 ; Zhou et al., 2024 ) and a significant body of empirical research has been dedicated to addressing this limitation ( Kazemnejad et al., 2024 ; Shen et al., 2023 ; Dai, 2019 ; Chi et al., 2022 ; Li et al., 2023 ; Press et al., 2021 ) . 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. (2017b) . 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. (2017b) 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., 2017b ) . 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] .