Efficient Attention and Long-Context Architectures

Dense self-attention compares every query position with every key position. The score matrix therefore grows quadratically with sequence length. That is before feed-forward activations and cached states are counted. The FlashAttention abstract opens with the flat version of the same sentence: “Transformers are slow and memory-hungry on long sequences, since the time and memory complexity of self-attention are quadratic in sequence length.”

The 2022 result then complicates the usual account of where the cost sits. The binding constraint is not arithmetic alone. It is the reads and writes between GPU high bandwidth memory and on-chip SRAM. A tiled, IO-aware attention that is mathematically exact — nothing approximated, no pair of positions dropped — gave a 15% end-to-end wall-clock speedup on BERT-large at sequence length 512, measured against the MLPerf 1.1 training speed record. It gave 3x on GPT-2 at sequence length 1K and 2.4x on Long Range Arena at sequence lengths of 1K–4K. It also produced the first Transformers to beat chance on Path-X (sequence length 16K, 61.4% accuracy) and on Path-256 (sequence length 64K, 63.1% accuracy). Two lessons follow. An exact method can outrun the approximations on the clock, so approximation is a choice to be justified rather than an inevitability. And before changing what attention computes, find out whether what it moves was the problem.

The second problem is not computational but epistemic. A model may accept a long prompt. It can still fail to retrieve, combine, or prioritize the evidence that matters. The rest of this lesson is mostly about measuring that failure rather than the first one.

Each strategy changes both cost and the information paths available to the model. Three of the six rows below have named instances that were measured rather than merely proposed. Read them as evidence about the family, not as product recommendations.

Sparse global links. BigBird is “a sparse attention mechanism that reduces this quadratic dependency to linear”: local windows, random links, and a handful of global tokens. Eleven authors published it in 2020. They proved that it “is a universal approximator of sequence functions and is Turing complete”, thereby preserving these properties of the quadratic, full attention model. Their analysis singles out the value of “O(1) global tokens (such as CLS), that attend to the entire sequence”. The pattern, they report, “can handle sequences of length up to 8x of what was previously possible using similar hardware”. Sparsity did not cost expressive power here. It cost a direct path. The global tokens buy that back.

Sparsity can also be chosen by the data instead of fixed in the architecture. Reformer replaces dot-product attention with locality-sensitive hashing, “changing its complexity from O(L^2) to O(L log L), where L is the length of the sequence”. It adds reversible residual layers too, “which allows storing activations only once in the training process instead of N times, where N is the number of layers”. Both halves arrived in one 2020 paper. They are two different budgets — the attention computation and the stored activations — and only attacking both turns into a hardware claim. Google Research stated the combined result in exactly those terms: “The novel application of these two approaches in Reformer makes it highly efficient, enabling it to process text sequences of lengths up to 1 million words on a single accelerator using only 16GB of memory.”

Recurrent or cached memory has its own measured instance. Transformer-XL carries state across segment boundaries, using a segment-level recurrence mechanism and a relative positional encoding scheme. It was published in 2019, and it quantified both halves of what that buys: “As a result, Transformer-XL learns dependency that is 80% longer than RNNs and 450% longer than vanilla Transformers, achieves better performance on both short and long sequences, and is up to 1,800+ times faster than vanilla Transformers during evaluation.” The 450% and the 1,800+ are different kinds of win. Carrying state lets the model see further. It also stops the model recomputing the same prefix at every step.

No approximation is free. Each protects some relationships and weakens others.

The linearized column is the one where the algebra is explicit enough to inspect. Express self-attention as a linear dot-product of kernel feature maps, then exploit the associativity of matrix products, and complexity falls from O(N^2) to O(N) in the sequence length N. Four authors did that in 2020. Reassociating the product means the dense score matrix is never formed at all. That is why the “avoids materializing dense scores” line below is a literal statement about the computation rather than a figure of speech. The same rearrangement changes what the model is: “We show that this formulation permits an iterative implementation that dramatically accelerates autoregressive transformers and reveals their relationship to recurrent neural networks.” On autoregressive prediction of very long sequences they report linear transformers up to 4000x faster than vanilla transformers.

That number is also where the trade sits. The speed comes from stepping through the sequence while carrying a running state of fixed size. A fixed-size state is a compression decision made in advance, before anyone knows which distant token the task will turn out to need. The comparison below is between evidence graphs, not between speeds.

A model can pass short benchmarks while failing these operational cases.

RULER turned that list into a benchmark in 2024. It extends needle-in-a-haystack with “variations with diverse types and quantities of needles”. It adds “multi-hop tracing and aggregation to test behaviors beyond searching from context”. It then ran 17 long-context models over 13 tasks. The result is the reason the first bullet is not enough on its own. “Despite achieving nearly perfect accuracy in the vanilla NIAH test, almost all models exhibit large performance drops as the context length increases.” And: “while these models all claim context sizes of 32K tokens or greater, only half of them can maintain satisfactory performance at the length of 32K.”

RULER is not the only such measurement, and the second one was built on a different principle. LongBench collects real bilingual tasks instead of synthesising haystacks whose contents it controls: “LongBench comprises 21 datasets across 6 task categories in both English and Chinese, with an average length of 6,711 words (English) and 13,386 characters (Chinese).” It appeared in 2024, and 8 LLMs were evaluated on it. It also tested the alternative that the next section proposes, and the finding is a qualified one worth carrying. Retrieval-style context compression helps models with weak long-context ability. It still lags models that are genuinely strong at long context. Two benchmarks, two constructions, one conclusion about advertised windows.

Do not begin with a target token count. Begin with the access pattern the product must support.

Step five has a named baseline. Retrieval-augmented generation dates to 2020. The paper defines “RAG models where the parametric memory is a pre-trained seq2seq model and the non-parametric memory is a dense vector index of Wikipedia, accessed with a pre-trained neural retriever”. It set the state of the art on three open-domain question-answering tasks, “outperforming parametric seq2seq models and task-specific retrieve-and-extract architectures”. On generation tasks, RAG models “generate more specific, diverse and factual language than a state-of-the-art parametric-only seq2seq baseline”. The reason given for the work is the governance one this lesson keeps returning to. For a model that stores everything in its weights, “providing provenance for their decisions and updating their world knowledge remain open research problems”.

Step five also has a boundary condition, from the LongBench results above. Retrieval-style context compression helped the models with weak long-context ability, and still lagged the models that were genuinely strong at long context. Read together, the two findings say something narrow. Retrieval is a substitute for long-context competence you do not have, and a complement to the provenance you need either way. So run it as a baseline in both directions. Measure the cost and the grounded accuracy of selecting less evidence. Then measure what a genuinely strong long-context model does with the same task, before assuming the retriever is the cheaper answer.

A longer window can simplify interfaces and preserve raw evidence, but it increases memory pressure and can invite irrelevant context. External retrieval adds system complexity and offers selective, inspectable evidence in return.

The measured results in this lesson do not converge on one architecture. That is the finding. An exact, IO-aware attention bought 15%, 3x and 2.4x on different workloads without approximating anything. Hashing-based sparsity bought O(L log L), and a million words on one accelerator with 16GB. Segment-level recurrence bought dependencies 450% longer and evaluation up to 1,800+ times faster. Kernel feature maps bought O(N) and up to 4000x on autoregressive prediction. Retrieval bought provenance. Each was measured on its own workload, against its own baseline. None of them is a default.

The best architecture may therefore combine local attention, compressed memory, and retrieval. Document which layer owns freshness, access control, citations, and deletion. Then test the assembled system at the positions and distractor levels where the published failures actually appear, not only at its maximum length.