Linear self-attention provably cannot beat linear regression on AR processes

After AI's run of success in language, images and video, plenty of people expected transformers to carry time series forecasting too. The reality is usually duller: plain linear regression often beats the heavyweight models on mean squared error. The paper under discussion gives a careful, rigorous account of why that happens, viewed through the lens of in-context learning.

In the authors' setup the input is not a plain history of observations but a Hankel matrix of windows of length p+1, where the last row is deliberately reserved for the future answer. Linear self-attention (LSA) — a stripped-down version with no softmax, but with clean math — operates on that matrix. The forecast is read out of the reserved slot. The payoff is that this discards incidental detail and lets you see the limits of expressivity directly in the formulas.

What attention is actually doing

The authors show that a single LSA layer is a linear functional of cubic features of the input sequence. That sounds rich, but in stationary autoregressions those same features gradually collapse onto the last p lags. With a long context, in other words, the best LSA predictor effectively coincides with ordinary p-lag linear regression. Attention extracts no fundamentally new signal — it only reorders and remixes linear information that was already available.

A provable gap at finite history

The real interest lies in finite context length. The theory delivers an unwelcome result: even an optimally tuned LSA, at any fixed number of observations, has expected MSE strictly higher than the classical p-lag linear predictor. The gap is structural rather than a symptom of bad training, and it shrinks no faster than 1/n. Adding depth (more LSA layers) helps but saturates — you can catch up with linear regression asymptotically, but you cannot pass it at finite n.

Where accuracy leaks out in multi-step rollouts

Real forecasting cares about more than a single step ahead. Here the authors turn to chain of thought: the model appends its own predictions step by step and keeps going. For AR(p) this pulls the forecast exponentially toward the process mean as the horizon grows. Even an ideal Bayesian linear predictor accumulates error with the horizon, but LSA starts out worse on the very first step and therefore loses on every step after it. The practical recommendation that follows: do not expect much of long CoT chains in series forecasting — the errors inevitably compound.

What it looks like on data

The authors back the theory with synthetic experiments on AR processes. Under teacher forcing, linear regression is consistently better than LSA; under CoT both models drift toward the mean over time, but LSA breaks down sooner. Scaling up history length and layer depth improves LSA, yet the gap to the linear baseline persists and closes only slowly.

What about softmax attention?

In an appendix the authors compare LSA with standard softmax attention under identical conditions. Softmax is slightly stronger empirically, which makes sense: it is more expressive. But the core conclusion does not change — even in that version the transformer does not beat the linear baseline on AR processes.

What all this means

• Always keep a linear baseline forecast on hand. If the data is close to AR/ARMA, it sets a bar that self-attention is under no obligation to clear.
• A long context helps, but it works no miracles: the gap closes slowly, roughly as 1/n.
• Layer depth without additional blocks will not save you. The temporal signal in series like these is mostly local; without strong nonlinear layers or purpose-built architectures the gain is limited.
• Be careful with multi-step CoT setups: errors pile up and drag the forecast toward the mean sooner than you would like.
• If your series are more complicated than linear ones (regime switches, seasonality, exogenous factors), look toward hybrids: linear heads plus nonlinear blocks, stochastic state-space models, or frequency and seasonal decompositions.

Why the findings matter

The paper cleanly separates questions of optimization from limits of representability. Even under ideal conditions, with the right weights, LSA on AR(p) cannot systematically outperform traditional linear predictors. That explains why on real datasets transformers often win only after strong nonlinear components and domain inductive biases are added — and sometimes lose outright to simple methods.

💾 Code