Provable Length Generalization in Sequence Prediction via Spectral Filtering
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 40 of its 44 references that are in the map. First posted on arXiv 1 Nov 2024.
Builds on
40 of 44 references.
References · 40
- 2017Attention Is All You Needcited by 59,932
- 2020Language Models are Few-Shot Learnerscited by 32,199
- 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
- 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,616
- 2021Efficiently Modeling Long Sequences with Structured State Spacescited by 2,424
- 2019Transformer-XL: Attentive Language Models Beyond a Fixed-Length Contextcited by 1,830
- 2021Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolationcited by 1,085
- 2019Introduction to Online Convex Optimizationcited by 793
- 2020Efficient Transformers: A Surveycited by 784
- 2022Simplified State Space Layers for Sequence Modelingcited by 776
- 2018Universal Transformerscited by 613
- 2021Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layerscited by 607
28 more
- 2020HiPPO: Recurrent Memory with Optimal Polynomial Projectionscited by 600
- 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
- 2023Resurrecting Recurrent Neural Networks for Long Sequencescited by 397
- 2023Hyena Hierarchy: Towards Larger Convolutional Language Modelscited by 388
- 2022Diagonal State Spaces are as Effective as Structured State Spacescited by 350
- 2023The Impact of Positional Encoding on Length Generalization in Transformerscited by 319
- 2015Unitary Evolution Recurrent Neural Networkscited by 291
- 2022Neural Networks and the Chomsky Hierarchycited by 214
- 2022Exploring Length Generalization in Large Language Modelscited by 204
- 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
- 2018Correcting Length Bias in Neural Machine Translationcited by 119
- 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 119
- 2015Neural GPUs Learn Algorithmscited by 118
- 2021Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networkscited by 108
- 2022Unveiling Transformers with LEGO: a synthetic reasoning taskcited by 105
- 2022KERPLE: Kernelized Relative Positional Embedding for Length Extrapolationcited by 84
- 2024Transformers Can Achieve Length Generalization But Not Robustlycited by 82
- 2023Generalization on the Unseen, Logic Reasoning and Degree Curriculumcited by 73
- 2023Length Generalization in Arithmetic Transformerscited by 64
- 2023Positional Description Matters for Transformers Arithmeticcited by 56
- 2019The Nonstochastic Control Problemcited by 52
- 2017Learning Linear Dynamical Systems via Spectral Filteringcited by 46
- 2020The EOS Decision and Length Extrapolationcited by 46
- 2018Spectral Filtering for General Linear Dynamical Systemscited by 37
- 2017Efficient Regret Minimization in Non-Convex Gamescited by 28
- 2024Universal Length Generalization with Turing Programscited by 25
- 2023Spectral State Space Modelscited by 20
- 2024Flash STU: Fast Spectral Transform Unitscited by 6
Built on by
Citing papers per year: 2025: 2; 2026: 1.
3 papers.