Every Token Looks Everywhere: The Quadratic Bill Behind Attention

TL;DR for operators

Long context becomes expensive for a specific architectural reason: standard self-attention allows every position to interact with every other position. In the usual formulation, that means $O(n^2 d)$ computation and $O(n^2)$ storage for attention-related matrices as sequence length $n$ grows. Hasi Hays’s mathematical monograph on attention¹ is useful because it connects that deployment constraint directly to the mechanism that makes attention powerful in the first place.

Attention is a learned routing operation. A representation asks for relevant information, other representations expose what they contain, compatibility scores determine weights, and the selected information is combined. Self-attention applies that process within one sequence, giving each position direct access to distant context instead of forcing information through a recurrent hidden state.

Two common assumptions need correction. First, self-attention does not inherently encode sequence order: without positional information, it is permutation equivariant. Second, visible attention weights can reveal interaction patterns without necessarily providing a faithful explanation of why a model produced a prediction.

For teams building long-document, conversational, retrieval-heavy, or multimodal systems, the practical choice is not “full attention or efficiency.” Sparse connectivity, low-rank projection, kernel-based approximation, and hardware-aware exact implementations attack different parts of the cost structure. The paper provides a framework for understanding those choices, but not a benchmark showing which one wins on a particular production workload.

When every token can inspect every other token

Suppose a product has to process a document twice as long as before. The additional cost does not come only from having twice as many tokens. Under standard self-attention, each new position participates in interactions with the rest of the sequence. The interaction structure itself expands quadratically.

That growth is the price of a valuable capability. Earlier recurrent sequence architectures had to compress prior information through an evolving fixed-dimensional hidden state. Attention replaces that narrow path with direct, learned access to available representations. A token near the end of a sequence can draw information from something much earlier without waiting for that information to survive a long chain of recurrent updates.

The same design that reduces the information-routing bottleneck creates a memory and compute bottleneck. For infrastructure teams, context length is therefore an architectural budget rather than merely a model configuration field.

Attention is learned information routing

The monograph gives classical attention, self-attention, and later Transformer components a common mathematical language. At its most general, attention assigns each available value a weight according to how compatible its key is with a query:

The query represents what information is being sought. Keys determine which items appear relevant to that query. Values contain the information eventually combined. This is more precise than describing attention as a layer that “looks at context”: it is a learned compatibility-and-aggregation mechanism.

Transformers use the vectorized scaled dot-product form:

The scaling factor matters. As the query-key dimension grows, unscaled dot products can grow in variance, pushing softmax toward increasingly saturated distributions. Dividing by $\sqrt{d_k}$ controls that effect.

This mathematical framing is valuable operationally because it lets teams reason from mechanism to resource use. Once every query is compared with every key, the quadratic sequence-length term is no longer an incidental implementation detail.

Sequence order does not come from self-attention itself

Direct token interaction can make attention feel inherently sequence-aware. Mathematically, bare self-attention does not know which position came first.

Without positional information,

where $\mathbf{P}$ reorders the sequence. Reorder the inputs, and the outputs are reordered correspondingly. This property is permutation equivariance.

For an order-sensitive task, positional information must therefore enter somewhere else. That distinction matters when teams modify positional schemes, extend context windows, or combine modalities: the attention operation provides relationships among representations, while another mechanism must encode what position or ordering means.

Multi-head attention then creates several learned relation spaces in parallel. Each head receives its own query, key, and value projections; the resulting representations are concatenated and projected back into the model space. Prior empirical work synthesized by the monograph reports heads associated with different positional, syntactic, semantic, or long-range patterns, but also substantial redundancy among some heads. Those observations come from heterogeneous earlier studies, not from a new controlled experiment in this paper.

Long-context efficiency has several different levers

Once sequence length becomes the constraint, “use efficient attention” is underspecified. The monograph groups the design space into approaches that reduce cost through different mechanisms.

The categories are not interchangeable. A sparse method changes connectivity. A kernel method may alter the mathematical approximation. A hardware-aware implementation can attack memory movement while retaining the exact attention operator.

Cognaptus inference: for teams serving long documents, retrieval contexts, extended conversations, or multimodal sequences, architecture selection should begin with the constrained resource. If accelerator memory is limiting deployment, the relevant design space can differ from a workload constrained primarily by latency, throughput, approximation tolerance, or engineering complexity.

The paper does not supply comparative production measurements that tell a team which route produces the best quality-per-dollar result for its workload.

Attention maps provide observability, not causal justification

Attention weights are unusually visible internal signals. That visibility creates a governance temptation: expose a heatmap, point to highly weighted tokens, and treat the result as an explanation.

The monograph explicitly warns against that step. Attention patterns can show which representations interact strongly under a particular attention operation, but those weights are not guaranteed to correspond to causal feature importance or to a faithful explanation of the final prediction.

For model developers, attention inspection can still be diagnostically informative. For audit, compliance, or user-facing explanation, the evidentiary bar is higher. An attention visualization shows an internal interaction pattern; the paper does not establish that the pattern explains the model’s decision.

The framework narrows the production question without answering it

The paper is strongest where the claims are mathematical: the query-key-value formulation, scaling behavior, permutation equivariance, and asymptotic computation and storage costs are derived directly. Its discussion of efficient methods, head specialization, interpretability, applications, and open research questions is a narrative synthesis of prior literature.

That distinction sets the practical boundary. The monograph does not report a newly executed standardized benchmark, a systematically enumerated review corpus, or a production comparison across efficient-attention implementations. Its broad empirical observations therefore inherit the varying models, tasks, and evaluation conditions of the studies it synthesizes.

For an architecture lead, the framework can identify what must be measured next: context length, accelerator-memory pressure, latency, throughput, acceptable approximation, required connectivity, and implementation constraints. It cannot replace workload-specific evaluation.

Treat context length as an information-routing budget

Attention solved one sequence-modeling problem by giving representations direct learned access to one another. That design choice also established the cost structure that long-context systems now have to manage.

The useful mental model is not that attention is universally expensive or that an efficient variant is universally better. Full attention purchases unrestricted pairwise access. Sparse, low-rank, kernel-based, and hardware-aware designs change the price by changing different parts of the mechanism.

Once that mechanism is explicit, context length becomes easier to reason about. It is a decision about how much interaction the workload needs, what resource constrains delivery, and which compromises the application can tolerate. The monograph does not choose that trade-off for operators. It makes the trade-off legible.

Cognaptus: Automate the Present, Incubate the Future.