Research map / Learning theory and algorithms / Kernels and regression theory
Provable Length Generalization in Sequence Prediction via Spectral Filtering
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Asymmetric-Regret to formalize length generalization in sequence prediction and proves that gradient-based spectral filtering trained with short context T^q achieves sublinear regret against full-context-T predictors for certain LDSs, with a two-autoregressive variant and tensorized filters, plus small synthetic and induction-heads/copy experiments.
Problem
Length generalization in online sequence prediction: learning with a short context length while competing with predictors that use a much longer context, especially for marginally-stable linear dynamical systems where long memory matters.
Approach
Defines Asymmetric-Regret, comparing a learner restricted to context L' against a benchmark with context L > L'. Shows that online gradient descent on spectral filters trained with short context T^q matches full-context spectral filtering up to O(sqrt(T)) for LDSs with constrained eigenvalues; adds a second autoregressive term to remove the spectral assumption, and tensorized filters for greater e
Key results
- Theorem shows Asymmetric-Regret of O~(sqrt(T)) for spectral filtering trained with context T^q on LDSs whose eigenvalues avoid the bad region; the two-autoregressive variant removes the spectral assumption for context at least T^{1/3}.
- On synthetic LDS experiments with T=2^14 and k=24, context length near T^{7/8} matches full-context spectral filtering on Region A eigenvalues, while T^{1/2} fails.
- On induction heads, vanilla STU trained at shorter lengths occasionally generalizes to length T, though inconsistently; tensorized filters improve length generalization on induction heads and copy, especially at smaller q.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train vanilla spectral filtering with context length T^{7/8} rather than full context T | Spectral Filtering with Limited Context · Synthetic LDS, eigenvalues sampled from Region A | prediction loss: T^{7/8} | Helped |
| Use context length T^{1/2} instead of a context length approaching T^{7/8} | Spectral Filtering with Limited Context · Synthetic LDS, eigenvalues sampled from Region A | prediction loss: T^{1/2} | Hurt |
| Train vanilla spectral filtering with limited context on eigenvalues in Region B | Spectral Filtering with Limited Context · Synthetic LDS, eigenvalues sampled from Region B | prediction loss | Hurt |
| Add a second autoregressive component, y_{t-2} (ablation) | Spectral Filtering with Limited Context · Synthetic LDS, eigenvalues sampled from Region B | prediction loss: \sqrt{T} | Helped |
| Tensorize the spectral filters (ablation) | STU · Induction heads | accuracy | Helped |
| Tensorize the spectral filters (ablation) | STU · Copy task | accuracy | Helped |
| Tensorize the spectral filters (ablation) | Spectral Filtering · Synthetic LDS | length generalization | No clear effect |
| Train vanilla STU with filters longer than the training context, without autoregressive components | STU · Induction heads | accuracy: T = 256 | Mixed |
Surprising findings
- Eigenvalues in a specific 'bad' range near 1 cause spectral filtering with context T^{1/2} to fail, even though they are not covered by the theory's guarantees.
- Vanilla STU generalizes to longer lengths without any architectural change, though inconsistently across seeds.
Limitations
- Theory restricted to noiseless linear dynamical systems with well-conditioned inputs and symmetric/PSD (nonnegative eigenvalue) A.
- Length generalization for nonlinear deep models (STU) is shown only empirically on small synthetic tasks, with inconsistent results.
- Tensorized filter regret theorem is not explained by theory for the empirical gains.
Experimental setup
Datasets: synthetic noiseless LDS sequences induction heads synthetic task copy task (synthetic)
Benchmarks: synthetic LDS prediction induction heads copy task
Metrics: prediction loss accuracy regret
Baselines: vanilla spectral filtering STU without tensorization full-context spectral filtering
Builds on: spectral filtering Spectral Transform Unit online gradient descent
Closest papers by meaning
- The Power of Second Order Methods for Sequence Preconditioning (NeurIPS 2026 · similarity 0.89)
- Understanding and Improving Length Generalization in Recurrent Models (ICML 2025 · similarity 0.89)
- Universal Sequence Preconditioning (NeurIPS 2025 · similarity 0.88)
- Predicting LLM Output Length via Entropy-Guided Representations (ICLR 2026 · similarity 0.87)
- Does Compression Imply Generalization? A Minimum Description Length Perspective (NeurIPS 2026 · similarity 0.87)
- Non-Asymptotic Length Generalization (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.