II · THE IDEA · ARTIFICIAL INTELLIGENCE
Transformer Memory Compression via Sliding Windows
▶ Listen · narrated
When a sequence doubles, ordinary attention memory roughly quadruples. That scaling wall is why long documents and long conversations become expensive long before the model runs out of ideas.
At a glance
- Core problem
- Standard attention memory scales with the square of sequence length
- Local fix
- Each position attends only inside a sliding window of neighbours
- Sparse memory
- Entity-supervised sparse access limits which memory slots are touched
- Linear path
- Linear transformers rewrite attention as a fast-weight update with linear cost
Think of a group conversation. Full attention is everyone writing a note to everyone else at once. The pile of notes grows very fast as you add people: twice the people, about four times the notes.
A sliding window is a rule that each person may only pass notes to neighbours within a few seats. The pile then grows roughly in step with the number of people, not with the square. Stack several rounds of neighbour-passing and a message can still drift down the row, but it takes hops.
Sparse entity memory is different: there is a big filing cabinet of facts about named things, and for each question you are allowed to pull only a few folders. You save effort by opening little of the cabinet, not by sitting closer together.
Linear attention as fast weights is a third picture. Instead of keeping every pairwise note, you keep one shared whiteboard. Each speaker erases and rewrites a little of that board; the next speaker reads the board. The whiteboard stays one size, so cost grows gently with the number of speakers.
All three ideas shrink memory. They shrink different things: distance of talk, number of folders opened, or whether pairwise notes exist at all.
Full self-attention forms QK^T scores with shape determined by sequence length n in both axes, so activations and commonly used backward buffers scale as O(n²) in that term (times heads and batch). Sliding-window local attention applies a banded mask (or never materialises off-band entries): each query sees at most w keys, giving O(n·w) attention storage for fixed w. Depth stacks expand the effective receptive field roughly as O(depth·w) along the sequence, without restoring single-layer global mixing.
Entities as Experts-style sparse memory keeps a large external store but routes each input to a small set of slots, with entity supervision shaping that routing. Runtime memory traffic tracks retrieves rather than full store size; errors concentrate on mis-retrieval and on information that was never entity-indexed.
Linear transformers avoid the n×n score matrix by algebraic reformulation of the attention update. The same recurrence admits a fast-weight reading: token-wise rank-one updates write a transient weight state used to map the next incoming features. Cost is linear in n for fixed state width, at the price of a different function class than softmax attention.
Limitations to track in systems work: window edge effects and the need for global or sparse side channels; load imbalance and supervision quality in entity retrieval; numerical stability and expressivity gaps under linearisation. Hybrid stacks are common because each method compresses a different part of the quadratic object.
Look closer
What the window actually stores
In full self-attention, every query is compared with every key, so the attention scores form an n-by-n block for a sequence of length n. A sliding window replaces that block with a band: each position keeps scores only for a fixed neighbourhood to its left and right. Memory then tracks the band width times n, not n squared. Positions far outside the band are simply never materialised in that layer’s attention matrix.
Sparse access is a different cut
Entities as Experts frames memory as a large store that is only sparsely read. Supervision tied to entities teaches the model which few slots matter for a given input, so the forward pass touches a small subset rather than the full table. That is compression by selection, not by locality: the surviving accesses need not be neighbours in the sequence, but they are few enough that the memory traffic stays manageable.
Linear attention as fast weights
Work on linear transformers shows that a carefully rewritten attention update can be read as a fast-weight programmer: a running state is edited by each token and then used to produce the next output, without ever forming the full score matrix. The arithmetic becomes linear in sequence length. Sliding windows, sparse entity memory, and linearised attention are therefore three different ways of refusing the same quadratic object.
The story
Standard transformer self-attention is simple to state and expensive to store. For a sequence of length n, queries and keys produce an n-by-n grid of scores. Activations, gradients, and the working buffers that hold them all feel that grid. Double the context and, all else equal, that particular cost grows by about four. On long documents, multi-turn logs, or any workload that wants the model to see far more than a short paragraph, the square becomes the binding constraint long before parameter count does.
Sliding-window local attention attacks the grid directly. Instead of letting every position look at every other position inside a layer, each position is allowed only a window of nearby keys—tokens within a fixed radius along the sequence. The score tensor thins into a band. Memory and compute for that layer then scale with n times the window width. If the window is treated as a constant chosen by the architect, the dependence on sequence length is linear. Nothing mystical happens to the values outside the window: they are simply absent from that layer’s attention pattern.
Locality is a strong inductive bet. Language and many other sequences do carry heavy short-range structure, so a banded pattern is not an arbitrary amputation. Information can still travel farther than one window if several layers are stacked, because a token that saw its neighbours can, in the next layer, influence tokens a window further on. The receptive field grows with depth, much as it does in convolutional stacks. What is lost is cheap, single-layer global mixing: a fact at position 2 and a question at position 2000 no longer meet inside one unrestricted attention hop unless some other pathway is added.
Sparse memory access, as in Entities as Experts, compresses along a different axis. Rather than restricting who may talk to whom by position, it restricts which external memory slots are read at all. Entity-level supervision gives the model a training signal for which few entries matter for the current input. The large store remains large on disk or in parameter space, but the runtime footprint tracks the number of retrieved experts, not the full table. That is useful when the long-range facts the model needs are sparse and nameable—entities—rather than a diffuse need for every token to see every other token.
Linear transformers take a third route. By reformulating the attention update so that it never materialises the n-by-n score matrix, they reduce the asymptotic cost in sequence length. The same mathematics can be read as a fast-weight programmer: each token writes a rank-one edit into a running weight state, and that state is what produces the next output. Memory is then dominated by the fixed-size state rather than by a growing score grid. The price is a change in the inductive bias of attention itself—what can be expressed, and how gradients flow—rather than a simple mask over the original scores.
None of these moves is free. Sliding windows buy linear memory at the cost of immediate global visibility. Sparse entity memory buys selective access at the cost of depending on supervision and on the quality of the retrieval decisions. Linearised attention buys asymptotic relief at the cost of altering the attention mechanism’s exact behaviour. In practice, systems often combine ideas: local windows for the dense backbone, plus a sparse or global side channel for the rare long link that still matters.
The shared editorial point is modest and mechanical. Quadratic attention memory is not an inevitable tax on “having context”; it is a consequence of storing all pairwise scores. Change what is stored—band the pairs, retrieve few slots, or replace the pair matrix with a running state—and the memory curve changes with it. Performance on long sequences is preserved only to the extent that the task still receives the interactions it actually needed. When those interactions are mostly local, or mostly entity-sparse, or expressible through a linearised state, the cheaper mechanism can look nearly as strong as full attention while remaining deployable.
Why it mattered then
As transformer contexts pushed beyond short paragraphs, the n-squared attention buffer stopped being a theoretical annoyance and became a systems bottleneck. Research split into complementary compressions: restrict the pattern (local windows), restrict the addresses (entity-supervised sparse memory), or rewrite the update so the matrix never appears (linear transformers as fast-weight programmers). Each line answered the same deployment pressure with a different inductive bias, and each made longer sequences feasible on hardware that could not hold a dense score grid.
Why it matters now
Long-context products still hit memory walls before they hit model capacity. Sliding windows, sparse memory reads, and linearised attention remain the practical toolkit for fitting more tokens into a fixed budget. Understanding that these are different refusals of the same quadratic object—locality, selection, reformulation—helps when choosing a stack, reading a paper, or deciding why a long prompt is slow even when parameter count looks modest.
The surprising detail
Linear attention’s link to fast-weight programming reframes a systems trick as an old neural idea: the sequence is not only attending over a buffer; it is writing a temporary weight matrix on the fly. Compression and “learning at test time” sit in the same equation. Sparse entity memory makes a related human-shaped move—remember named things densely, not every token equally—which is why supervision on entities can matter as much as raw length.
What is disputed
The two cited lines of work address sparse entity memory and linear transformers as fast-weight programmers. Sliding windows are treated here as the editorial frame for local attention’s memory band, not as a result claimed inside those specific papers. Exact preservation of quality on long sequences depends on task structure and is not guaranteed by the asymptotic saving alone.
Remember this
Quadratic attention memory comes from storing all pairs. Windows, sparse entity reads, and linear fast-weights each refuse that grid differently.
Test yourself
A service wants longer prompts without growing GPU memory like n squared. You can band attention with a sliding window, retrieve a few entity memory slots, or switch to a linear fast-weight form of attention. For each choice, name the interaction you are most at risk of weakening.
Sliding window: single-layer global pairwise mixing between distant positions; long-range links must hop across layers or use another path. Sparse entity memory: facts that are not tied to the supervised entities, or that need dense many-to-many token interaction rather than a few retrieved slots. Linear fast-weight attention: behaviours that depended on the exact full softmax attention matrix, since the rewrite changes what the layer computes even though cost becomes linear in length.
Go deeper
- [2004.07202] Entities as Experts: Sparse Memory Access with Entity Supervision · arxiv.org
- [2102.11174] Linear Transformers Are Secretly Fast Weight Programmers · arxiv.org
Image: Original diagram, The Daily Triptych. Licence: Original work. Source.