Informer and ProbSparse Attention

Informer targets long time-series forecasts, where sequences of thousands of timesteps make ordinary self-attention's quadratic cost prohibitive. Its authors observed that a trained attention distribution is usually dominated by a small number of queries whose attention weights are sharply peaked on a few keys — most queries produce an almost-uniform, uninformative spread over all keys instead. Only the "peaked" queries are actually doing useful work.

ProbSparse attention exploits this by measuring, cheaply, how far each query's attention distribution is from uniform (using a sampled approximation rather than computing full attention first, which would defeat the purpose), then keeping only the top handful of queries by that measure — typically on the order of $\log n$ out of $n$ total queries. Full, exact attention is computed only for those selected queries against all keys; the remaining queries are simply assigned an average of the values, since their attention pattern carries little information anyway. This drops attention's cost from $O(n^2)$ to roughly $O(n \log n)$.

Informer combines ProbSparse attention with a "distilling" step between layers that halves sequence length progressively, letting it forecast well beyond the 1,000-step horizons where standard transformers become computationally impractical.