II · THE IDEA · ARTIFICIAL INTELLIGENCE
Sliding Window Attention for Long Sequences
▶ Listen · narrated
A long document can exhaust ordinary transformer attention long before the model runs out of something useful to say. The fix is not a larger machine, but a smaller field of view.
At a glance
- What it is
- Self-attention limited to a fixed window of neighbouring tokens
- Full attention
- Every token attends to every other; cost scales with length squared
- Windowed cost
- Linear in sequence length when the window size is held fixed
- Longformer
- Combines sliding windows with sparse global attention on selected tokens
- Receptive field
- Grows with depth as stacked layers compose local windows
Think of a long queue of people passing notes. In ordinary transformer attention, every person may hand a note to every other person in one round. The number of notes is roughly the square of the crowd size, which becomes unmanageable as the queue grows.
Sliding window attention changes the rule. Each person may only pass notes to a fixed number of neighbours on either side — a window. Double the queue and you only double the notes, because the window size stays the same.
People far apart can still hear from each other eventually, because the exercise happens in many rounds (layers). A note can travel a few places each round and cross the queue over time. You can also appoint a few runners who are allowed to talk to everyone; Longformer does something like that with global tokens. Another family of methods, discussed in the Linear Transformers work, keeps a different rule altogether: it changes the arithmetic so the full square of notes never has to be written down. Same wish for lower cost; different rulebook.
Standard scaled dot-product self-attention forms an n by n matrix of scores, QK^T, with time and memory Θ(n²d) dominated by that matrix for long n. Sliding window attention replaces the dense score matrix with a banded one: query i attends only to keys in [i − r, i + r] (or a one-sided or dilated variant), for fixed window width w ≈ 2r + 1. Non-window entries are masked and need not be materialised. Cost per layer falls to Θ(n w d) for fixed w.
Stacked layers compose receptive fields. With contiguous windows, information from position j can reach i after enough layers that |i − j| is covered by the sum of per-layer spans. Dilated windows increase span per attended position by sampling with gaps, raising receptive-field growth without raising w. Longformer pairs this local pattern with a sparse set of global positions whose rows and columns in the attention pattern remain full; those positions restore selected long-range pathways while the bulk of the matrix stays banded.
Linear complexity is not unique to windowing. Linear Transformer attention uses a feature map φ such that attention weights factor through φ(Q)φ(K)^T, allowing the sum over keys to be reassociated so that an n by n matrix is never formed; cost becomes linear in n under suitable φ. That work also frames the resulting recurrence as fast weight programming. The inductive bias differs sharply from windows: there is no hard locality mask unless one is added. Choice between banded sparse attention and kernelised linear attention is therefore a bias and systems choice, not only an asymptotic one.
Limitations of pure windows include weak single-layer long-range paths, sensitivity of effective context to depth and dilation, and load imbalance at sequence edges. Global tokens mitigate the first issue only for the positions so designated. Implementations must still handle causal masks, batching of variable lengths, and efficient banded kernels; a naïve dense matrix with a mask does not deliver the theoretical saving.
Look closer
The attention matrix becomes a band
In full self-attention the score matrix is dense: every query position has a non-zero pathway to every key. Under a sliding window of width w, only a diagonal band survives. Entries outside that band are masked and never computed. The band’s width is independent of how long the sequence is, which is why memory and time track n rather than n² once w is fixed.
Depth buys back range
A single layer with a modest window cannot see far. Stack several layers and information can hop across the sequence one window-width at a time, so the effective receptive field grows with depth. Longformer also describes dilated windows, which skip positions inside the window and stretch that field further without a matching rise in cost per layer.
Local is not always enough
Some tokens need a document-wide view — a classification token, or sparse anchors in a long article. Longformer therefore keeps a small set of global tokens that may attend to, and be attended by, the full sequence, while the bulk of positions stay inside the sliding window. The global set is sparse on purpose; densifying it would restore quadratic cost.
The story
Ordinary transformer self-attention lets every position gather from every other position in one step. That full view is powerful, and expensive. Both the compute and the memory needed for the attention scores scale with the square of the sequence length. Double the tokens and you roughly quadruple the attention work. For short passages this is tolerable. For long documents it becomes the binding constraint long before other parts of the model do.
Sliding window attention answers that pressure by changing the pattern of who may look at whom. Each token is allowed to attend only to a fixed neighbourhood — a window of width w centred on itself (or otherwise placed along the sequence). Positions outside the window are masked. Because w does not grow with the sequence, the number of score entries that must be formed is proportional to n times w, not n times n. Hold the window fixed and the attention cost becomes linear in length.
The obvious objection is loss of range. A token in layer one truly cannot see beyond its window. The architecture does not leave the matter there. In a stack of layers, each layer’s outputs feed the next, so a signal can travel farther with depth: after L layers the receptive field is on the order of L times the window span, assuming ordinary contiguous windows. Dilated windows, as described for Longformer, insert gaps inside the window so that the same number of attended positions covers a wider span, at the cost of a more porous local view.
Longformer’s design does not rely on the window alone. It mixes the sliding pattern with a small number of global attention positions. Those positions are chosen for the task — often a classification token, or a handful of evenly spaced anchors — and they retain full-sequence access. Everything else stays local. The global set must remain sparse; if it grew with n, the asymptotic saving would erode.
This is one route to linear complexity, not the only one. The Linear Transformers work reaches linear cost by a different route: rewriting attention in a kernel or feature-map form so that the expensive token-to-token score matrix need not be materialised at all, and showing an equivalence between that form and fast weight programmers. Sliding windows sparsify the pattern of attention; linearised attention changes the algebra. They address the same quadratic bottleneck with unlike mechanisms, and they carry unlike inductive biases. A window enforces locality by construction. A linearised kernel does not, unless further structure is added.
In practice the window size, the optional dilation schedule, and the placement of global tokens are design choices that trade context against cost. Too narrow a window and long-range dependencies must climb many layers or pass through the global bottleneck. Too wide and the linear saving shrinks. The method does not remove that trade-off; it makes the trade-off explicit and tunable in units of tokens rather than in units of hardware alone.
Why it mattered then
When Longformer was introduced, transformer models were already the default for many language tasks, yet their quadratic attention made long documents awkward. Practitioners split text into overlapping chunks, discarded context, or simply avoided lengths that would not fit. A pattern of attention that stayed linear in length, while still stacking into a usable receptive field and admitting a few global tokens, offered a way to keep the transformer block and still read farther. The Linear Transformers line of work, arriving in a nearby period, showed that the quadratic matrix was not the only algebraic path either — reinforcing that full dense attention was a design choice, not a necessity, for sequence models that wanted scale in the length dimension.
Why it matters now
Sequence lengths in deployed models have grown, and with them the fraction of time and memory spent inside attention. Sliding window patterns, and hybrids that mix local windows with sparse global or selected full rows, remain a practical lever whenever the workload is dominated by long inputs and the task has a natural local structure — documents, high-resolution signals, or any stream where nearby tokens carry most of the immediate dependency. They also remain a clear baseline against which kernelised, low-rank, and other linear-complexity attentions are judged: same asymptotic claim, different bias about which interactions matter.
The surprising detail
Sliding window attention and linearised kernel attention both advertise linear cost in sequence length, yet they are not interchangeable approximations of the same thing. One hard-wires locality into the support of the attention matrix; the other keeps a full (or feature-mapped) interaction but avoids forming the n by n matrix. The Linear Transformers analysis goes further and identifies the linearised form with fast weight programmers — a connection that is about the update rule and memory of the layer, not about neighbourhoods on a page. Two remedies for one bottleneck can still be solving different problems underneath.
What is disputed
Longformer-style windowing and linearised kernel attention both target the quadratic bottleneck, but published comparisons depend on task, length, and implementation detail. Neither approach universally dominates the other; locality bias helps some long-document workloads and hinders others that need dense long-range mixing without privileged global positions.
Remember this
A sliding window makes attention linear in length by restricting each token to a local band; range then comes from depth, dilation, and a few global tokens — not from the full matrix.
Test yourself
A model uses pure sliding-window attention with window width w and L layers, and no global tokens. Why can a token at one end of a long sequence still influence a token at the other end, and what determines whether that influence actually arrives with any strength?
Influence can propagate across layers: each layer lets a signal move by roughly w positions (or farther with dilation), so after L layers the theoretical receptive field spans on the order of L times the per-layer span. Whether a usable signal arrives is another matter. It must survive L successive weighted mixes, compete with other local sources at every hop, and fit the dilation pattern if gaps are used. Depth gives a path; it does not guarantee a strong path. That is one reason Longformer-style designs add sparse global tokens for dependencies that should not have to travel hop by hop.
Go deeper
- [2004.05150] Longformer: The Long-Document Transformer · arxiv.org
- [2102.11174] Linear Transformers Are Secretly Fast Weight Programmers · arxiv.org
Image: Original diagram, The Daily Triptych. Licence: Original work. Source.