Full self-attention lets every token attend to every other token: for a sequence of length N that costs O(N²) score computations, which becomes impractical once N reaches thousands of tokens (a long document, a codebase, a chat history).
Long-context transformers instead split the sequence into fixed-size segments of length W and process them one at a time. Inside a segment, attention stays local and cheap:
Attention(Q,K,V) = softmax(QKᵀ / √d) V
Cost per segment ≈ W · (W + M) (window attends to itself + cached memory)
Cost for full seq ≈ N² (every token attends to every other token)
The key trick — segment-level recurrence, as used in Transformer-XL — is to cache the hidden states of the previous segment as a fixed-size memory of M tokens (with gradients stopped, so it's cheap to keep around) and let the current window attend to "window + memory" instead of just the window:
h̃τ = [ stop_grad(memτ-1) ; hτ ]
Kτ, Vτ = h̃τ Wk, h̃τ Wv Qτ = hτ Wq
memτ = last M rows of h̃τ
Because memory is carried forward segment after segment, information can in principle propagate arbitrarily far back — the model's effective receptive field grows with the number of segments processed, even though the compute cost of every single step stays O(W·(W+M)), never O(N²). That's the same idea behind sliding-window local attention (Longformer, Mistral) and the "chunk + carry a running summary" pattern used in retrieval pipelines for documents that don't fit in one context window.
Note on the cumulative-savings readout: it sums W·(W+M) once per segment in the current pass through the sequence (resetting cleanly to 0 at segment 1, not left over from a previous lap) and compares that running total against the single one-time cost N² of full attention over the whole sequence — so the percentage climbs monotonically within a pass instead of needing to be clamped away from a spurious negative value.
- Window size W — how many tokens are processed together in one local-attention step.
- Memory M — how many hidden states from the previous segment are cached and kept visible to the next window.
- Effective context — the cumulative span of the sequence that has fed into the recurrence chain so far, shown against the true sequence length N.
- Drag the tape to pan when the sequence is wider than the view; scroll/pinch to zoom.