Attention Complexity: Quadratic Scaling, Memory Limits

The power of self-attention comes with a price. Every token attends to every other token, creating $n^2$ pairwise interactions for a sequence of $n$ tokens. This quadratic scaling is both the source of attention's strength and its primary limitation. Understanding the computational and memory costs of attention is essential for working with transformers at scale, choosing appropriate model configurations, and knowing when alternative architectures might be necessary.

Think of it this way: if you have a classroom of 30 students and every student must pass a note to every other student, you need $30 \times 30 = 900$ note exchanges. If the class doubles to 60 students, you need $60 \times 60 = 3600$ exchanges, four times as many. Self-attention faces exactly this combinatorial growth with every token in a sequence. At modest sequence lengths, this overhead is affordable. At the scale of entire documents, codebases, or long conversations, it becomes the central engineering challenge of modern language models.

The quadratic complexity is not an accident or an oversight. It is a direct consequence of what makes attention powerful: every token can consult every other token in a single operation. There are no intermediaries, no bottlenecks from sequential processing, no information that must travel through a chain of steps before reaching its destination. This directness is why transformers capture long-range dependencies so much more effectively than recurrent networks. The cost is that the number of computations grows as the square of the context, rather than linearly.

In this chapter, we analyze the complexity of attention from multiple angles: time complexity measured in floating-point operations (FLOPs), memory requirements for storing attention weights, and practical scaling limits. We compare attention to recurrent models and explore why the quadratic cost becomes prohibitive for long sequences. We also survey a range of efficient attention variants, which attempt to preserve the quality of full attention while reducing its computational footprint.

By the end of this chapter, you will have a precise, quantitative understanding of where the costs come from, which hardware constraints matter most in practice, and how researchers have approached breaking the quadratic barrier. This understanding is not merely academic. It determines which models you can run, which tasks require specialized infrastructure, and which architectural choices are worth the trade-off at a given scale.

Self-attention's computational cost is best understood not as a formula but as a structural property of the mechanism itself. Before we count operations, it helps to ask: why is a quadratic cost inevitable here, and is there any way around it?

The answer is that full self-attention is defined as exhaustive pairwise comparison. The mechanism works by asking, for every token, "how relevant is every other token to me right now?" This question cannot be answered without computing a relevance score between every pair. If you skip any pair, you may miss a critical dependency. A pronoun might refer to a noun fifty tokens back. A closing bracket might need to match an opening bracket hundreds of tokens earlier. The mechanism is designed to handle exactly these cases, and handling them requires examining all pairs. The cost is the price of generality.

To understand why attention becomes expensive, we need to trace through exactly what happens when self-attention processes a sequence. The mechanism is elegant but computationally demanding, and the cost comes from a single, fundamental fact: every token must interact with every other token.

Imagine you're in a room with $n$ people, and everyone needs to have a brief conversation with everyone else. With 10 people, that's $10 \times 10 = 100$ conversations. With 100 people, it's $100 \times 100 = 10,000$ conversations. The number of interactions grows as the square of the group size. Self-attention faces exactly this scaling challenge.

The quadratic cost follows from the requirement to evaluate all pairwise relevances exactly. There is no clever algorithm that evaluates all pairwise relevances in fewer than $O(n^2)$ steps while remaining exact. Algorithms that claim linear attention complexity always involve an approximation: they find a way to avoid computing all pairs exactly, at some cost to expressiveness or accuracy. This distinction between exact and approximate attention is a recurring theme in the efficiency literature, and understanding the quadratic baseline is essential for evaluating those trade-offs.

Self-attention proceeds through three distinct operations, each contributing to the overall computational cost. These three stages correspond exactly to the formula you have seen before in this book, but here we examine them through the lens of cost rather than function. Each stage has a well-defined computational profile, and understanding them separately makes the total complexity easy to build up from first principles.

The three stages are:

1. Computing attention scores: Each token asks "how relevant is every other token to me?" This requires comparing all $n$ tokens against all $n$ tokens, producing an $n \times n$ grid of relevance scores.

2. Applying softmax: The raw scores are converted into proper attention weights that sum to 1, allowing us to interpret them as a probability distribution. This normalizes along each row of the score matrix.

3. Computing outputs: Each token gathers information from all other tokens, weighted by the attention scores, to produce its contextual representation. This is a weighted sum over value vectors.

The first and third steps are where the quadratic cost emerges. Step two is also quadratic, but it is dominated by the other two when the model dimension is large. Let's examine each stage carefully, counting operations precisely.

The heart of self-attention is measuring pairwise relevance between tokens. Given a sequence of $n$ tokens, we need to compute how strongly each token should attend to every other token. This is done by comparing query vectors against key vectors using the dot product. You can think of the query as a question and the key as an index: the dot product measures how well a token's question matches another token's index entry.

The reason we use a matrix multiplication here, rather than computing each score individually in a loop, is efficiency. Modern hardware, especially GPUs and TPUs, is designed to execute large matrix multiplications at peak throughput. Expressing the operation as a single $QK^T$ multiplication allows the hardware to exploit its full parallelism. The result is still the same $n^2$ numbers, but computed much faster than $n^2$ separate dot products would be.

Mathematically, we arrange all queries into a matrix $Q$ and all keys into a matrix $K$, then compute:

where:

• $S$: the $n \times n$ attention score matrix, where $S_{ij}$ measures how much token $i$ should attend to token $j$
• $Q$: the query matrix with shape $n \times d_k$, containing one query vector per token
• $K^T$: the transposed key matrix with shape $d_k \times n$, rearranging the key vectors for efficient matrix multiplication
• $n$: the sequence length (number of tokens)
• $d_k$: the dimension of each query/key vector (typically 64 in standard transformers)

Why does this produce $n^2$ values? Each row of $Q$ (one token's query) gets multiplied against every column of $K^T$ (every token's key), producing one score per pair. With $n$ rows and $n$ columns, we get an $n \times n$ grid of scores.

The computational cost of this matrix multiplication is substantial. Each entry in the output matrix requires $d_k$ multiplications and $d_k - 1$ additions. With $n^2$ entries, the total operation count is $n^2 \cdot d_k$.

The critical observation is that this score computation already scales as $O(n^2 d_k)$. The $n^2$ term is unavoidable: we cannot know which token pairs are important without examining all of them. Even in cases where the final attention weights are sparse (most tokens barely attending to most others), we still must compute all the raw scores before we can discover which ones are large. The sparsity only emerges after the computation, not before it.

Raw dot products can be any real number, positive or negative, with no upper bound. To use them as weights for a weighted average, we need to transform them into a valid probability distribution. The softmax function accomplishes this by exponentiating each score and normalizing within each row.

The key insight is that softmax operates independently on each row of the score matrix. Each row corresponds to one query token, and its $n$ scores express how much that token should attend to each of the $n$ positions. Softmax converts these $n$ arbitrary numbers into $n$ non-negative weights that sum to exactly 1. Think of it as converting raw relevance signals into a proper distribution over positions to attend to.

For each token $i$, softmax converts its $n$ raw scores into $n$ attention weights that sum to 1. This involves:

1. Computing $\exp(S_{ij})$ for each of the $n$ scores (making them all positive)
2. Summing these exponentials across the row
3. Dividing each exponential by the sum

Each row requires approximately $3n$ operations (exponentiate, sum, divide), and with $n$ rows, the total is $O(n^2)$. While still quadratic, this is dominated by the $O(n^2 d_k)$ cost of score computation when $d_k$ is large. In practice, the softmax step is rarely the performance bottleneck, but it does introduce a numerical subtlety: computing $\exp$ of large values causes overflow. The standard remedy is to subtract the row maximum before exponentiating, which leaves the softmax output unchanged (the constant cancels in the numerator and denominator) but keeps all values in a numerically safe range.

The final step uses the attention weights to compute a weighted combination of value vectors. Each token's output is a blend of all tokens' values, weighted by attention. You can think of this as a soft lookup: instead of retrieving a single value at a specific position, each token retrieves a smooth mixture of all values in the sequence, weighted by how relevant each position was determined to be in Stage 1.

The operation computes a new representation for each of the $n$ tokens. Each token's new representation aggregates information from every other token in the sequence, scaled by attention weights. Tokens that received high attention scores contribute more to the output; tokens with near-zero attention weight contribute almost nothing.

The formula for this aggregation is:

where:

• $\text{softmax}(S)$: the $n \times n$ attention weight matrix, with each row summing to 1
• $V$: the value matrix with shape $n \times d_v$, containing one value vector per token
• $d_v$: the dimension of each value vector (typically equal to $d_k$)

This is another matrix multiplication: $(n \times n) \cdot (n \times d_v)$ produces an $n \times d_v$ output. Each of the $n \cdot d_v$ output elements requires $n$ multiply-accumulate operations (summing across the $n$ positions), giving $n^2 \cdot d_v$ total operations.

This step is just as expensive as score computation. Notice that both of the dominant operations involve an $n \times n$ intermediate matrix: in Stage 1 we create this matrix, and in Stage 3 we multiply by it. This $n \times n$ structure is the crux of attention's quadratic scaling, and it is also the primary target of memory-efficient implementations like FlashAttention, which avoid materializing the full $n \times n$ matrix in memory at once.

Now that we have analyzed each stage individually, we can combine the costs to get the total complexity of a single self-attention operation. This summary is important because it makes the $n^2 d$ scaling explicit and shows that neither the softmax step nor the $d$ dimension can offset the quadratic term.

Summing the costs from all three stages:

where:

• $n$: sequence length
• $d_k$: query/key dimension
• $d_v$: value dimension
• $d$: model dimension (typically $d_k = d_v = d/h$ for $h$ attention heads)

The simplification to $O(n^2 d)$ reflects that $d_k$ and $d_v$ are both proportional to the model dimension $d$. In standard transformers, each head operates on $d/h$ dimensions, but since we have $h$ heads processing in parallel and concatenating their outputs, the total complexity across all heads scales with the full model dimension.

It is worth pausing here to appreciate what this formula tells us. Two factors control the cost: the sequence length squared ($n^2$) and the model dimension ($d$). These two factors contribute very differently to the total. Doubling $d$ doubles the cost. Doubling $n$ quadruples it. For any sequence where $n > 1$, the sequence length term dominates. A model with $n = 2048$ and $d = 768$ spends roughly $2048^2 / 768 \approx 5,461$ times more computation on the $n^2$ factor than on the $d$ factor. This asymmetry is exactly what makes sequence length the central bottleneck in transformer scaling.

Let's trace through a concrete small example to make the formula visceral. Consider a single-head attention layer with sequence length $n = 4$ (four tokens), query/key dimension $d_k = 3$, and value dimension $d_v = 3$.

Stage 1: Score computation. The query matrix $Q$ has shape $4 \times 3$ and the key matrix $K$ has shape $4 \times 3$. Computing $S = QK^T$ produces a $4 \times 4$ matrix. Each of the 16 entries requires 3 multiplications and 2 additions (a dot product of length 3), totaling $16 \times 3 = 48$ multiplications.

Stage 2: Softmax. We apply softmax to each of the 4 rows of $S$. Each row has 4 elements, requiring 4 exponentiations, 1 sum (over 4 values, so 3 additions), and 4 divisions. Approximately $4 \times (4 + 3 + 4) = 44$ operations.

Stage 3: Output computation. The softmax weight matrix has shape $4 \times 4$ and the value matrix $V$ has shape $4 \times 3$. The product has shape $4 \times 3$. Each of the 12 output entries requires 4 multiplications and 3 additions, totaling $12 \times 4 = 48$ multiplications.

The total is dominated by Stages 1 and 3: approximately $48 + 48 = 96$ multiplications (plus roughly the same number of additions). Using our formula $2n^2 d_k = 2 \times 16 \times 3 = 96$, we recover exactly this number. The formula works.

Now compare with scaling to $n = 8$ (doubling the sequence length). Stage 1 becomes $64 \times 3 = 192$ multiplications (4x more). Stage 3 becomes $64 \times 3 = 192$ multiplications (4x more). The total scales by exactly 4x, as the quadratic formula predicts. Every doubling of $n$ multiplies the operation count by 4, regardless of what $d$ is. This is the essential arithmetic that makes long sequences expensive.

This analysis reveals the fundamental scaling behavior of self-attention. The two key findings are:

• Quadratic in sequence length: Doubling $n$ quadruples the computation. This is the defining characteristic that limits context length.
• Linear in model dimension: Doubling $d$ only doubles the computation. Making models wider is relatively cheap.

The quadratic term dominates for long sequences. At $n = 1000$ tokens with $d = 768$ (GPT-2 dimensions), the $n^2 = 1,000,000$ factor far exceeds the $d = 768$ factor. Understanding this asymmetry helps when reasoning about transformer scalability.

The key insight is that this asymmetry shapes all of modern LLM engineering. When practitioners want more capable models, they often increase model depth and dimension, which costs linearly. When they want models that understand longer documents, they face a quadratic penalty. This is why context length has historically lagged so far behind model parameter counts: a 10x increase in context length requires 100x more attention computation, while a 10x increase in parameters (achieved through wider or deeper models) costs only 10x more. The entire field of efficient attention is essentially an attempt to change this ratio.

The theoretical complexity $O(n^2 d)$ tells us about relative growth rates, but it hides constant factors and additive terms that matter enormously in practice. To see the actual numbers, let's build a function that calculates exact FLOPs for self-attention. This exercise converts the abstract complexity formula into concrete operation counts that can be compared against hardware throughput specifications.

The function mirrors our three-stage analysis: score computation contributes $n^2 \cdot d$ operations, softmax contributes $3 \cdot n^2$ operations, and output computation contributes another $n^2 \cdot d$ operations. Notice that the softmax term is negligible relative to the others when $d \gg 3$, which is always true in practice ($d$ is typically in the hundreds). This confirms that the two matrix multiplications, not the softmax, are the computational bottleneck.

The plot confirms the quadratic relationship. Moving from 512 to 1024 tokens quadruples the computation, and moving from 1024 to 2048 quadruples it again. At the right edge of the plot, we're computing nearly 100 billion operations for a single attention layer.

Computation is only half the story. Memory consumption often becomes the limiting factor before compute does. Self-attention requires storing several large tensors, and the memory profile of these tensors follows the same quadratic pattern as the computation, with some additional complications that make memory management especially challenging in practice.

Think of memory pressure as a different kind of constraint than compute. With compute, the question is how long something takes. With memory, the question is whether it fits at all. A computation that is slow can still complete given enough time; a computation that exceeds available memory simply fails, often abruptly and without a clear error message. This binary nature of memory constraints makes them especially important to understand before designing or deploying attention-based systems.

During a forward pass, the key memory consumer is the attention weight matrix itself. Every element of this $n \times n$ matrix must be materialized in memory before the output can be computed in the standard implementation. For training, the situation is worse: the entire matrix must be kept in memory throughout the forward pass so that gradients can be computed during the backward pass. For each layer, this quadratic memory cost persists throughout the backward computation rather than appearing as a momentary spike.

The memory bottleneck is what motivated the development of FlashAttention, which we will discuss later in this chapter. The key insight behind FlashAttention is that the forward and backward passes can be restructured to process the attention matrix in small blocks that fit in the GPU's fast on-chip memory (called SRAM), rather than writing the full $n \times n$ matrix to the slower off-chip memory (HBM). This dramatically reduces memory transfers, even though it performs the same total number of floating-point operations.

The attention weight matrix has shape $n \times n$, where $n$ is the sequence length. This is the dominant memory consumer in standard attention implementations. For a single attention head, this matrix contains $n^2$ elements. With $h$ heads, we store $h \cdot n^2$ values. Using 32-bit floats (4 bytes each), the memory requirement is:

where:

• $M_{\text{attn}}$: memory required for attention matrices
• $h$: number of attention heads
• $n$: sequence length
• $4$: bytes per element for 32-bit floats (fp32)

For 16-bit floats (common in modern training with fp16 or bf16), this halves to $2 \cdot h \cdot n^2$ bytes. The quadratic dependence on $n$ means that doubling the sequence length quadruples the memory requirement. This is the same quadratic relationship we saw for compute, but memory is a harder constraint: you can always wait longer for computation, but you cannot wait your way around a memory limit.

A complete forward pass through attention requires storing several tensors simultaneously. Understanding this breakdown helps you predict memory usage and design systems that fit within hardware constraints. A complete forward pass through attention requires storing:

• Query, Key, Value matrices: Each is $n \times d$, totaling $3nd$ elements. These scale linearly with sequence length.
• Attention scores/weights: $n^2$ per head, $hn^2$ total. These scale quadratically and dominate for long sequences.
• Output before projection: $n \times d$ elements. Linear in sequence length.
• Intermediate activations for backpropagation: Often requires keeping the attention matrix and pre-softmax scores in memory for the duration of the backward pass.

During training, gradient computation doubles many of these requirements. The optimizer state, which stores momentum and variance estimates for every parameter in Adam-style optimization, adds further overhead that scales with model size rather than sequence length. The total memory footprint during training is commonly estimated as 12 to 20 bytes per parameter for the model and optimizer states, plus the activation memory (dominated by the attention matrices) which scales with batch size and sequence length.

The heatmap shows that memory grows quadratically with sequence length but only linearly with model size. Doubling from 2048 to 4096 tokens has a larger impact than moving from GPT-2 Small to GPT-2 Large. For truly long sequences, even small models hit memory limits.

To appreciate why the quadratic cost matters, let's compare attention to recurrent neural networks. Both architectures process sequences, but their computational patterns differ fundamentally. Understanding this comparison is important for two reasons. First, it contextualizes when attention's quadratic cost is a problem versus when it is irrelevant. Second, it makes precise the trade-off that motivated the transformer architecture: you pay more computation per token in exchange for dramatically shorter information paths.

Before transformers, recurrent networks (LSTMs and GRUs) were the dominant architecture for sequence modeling. These networks processed sequences token by token, maintaining a fixed-size hidden state that summarized everything seen so far. This sequential nature made them efficient in terms of total operations, but it created a critical weakness: information from early in the sequence had to propagate through many time steps to influence late positions. In a 1000-token sequence, information from the first token must survive 999 update steps to reach the last position. Each step involves a learned transformation, and information tends to degrade through this chain, a problem known as the vanishing gradient.

Attention sidesteps this problem entirely by connecting any two positions directly in a single operation. The cost of this directness is the quadratic scaling. Whether this trade-off is worth it depends on the sequence length, the nature of the task, and whether the long-range dependencies you care about are dense enough to justify the overhead.

The recurrent architecture's cost structure is fundamentally different from attention's. Rather than computing all pairwise interactions at once, an RNN processes tokens one at a time, updating a hidden state at each step. This sequential structure has practical consequences for both complexity and parallelizability.

An RNN with hidden dimension $d$ processes each of $n$ tokens sequentially. At each timestep $t$, the hidden state update follows:

where:

• $h_t$: hidden state at timestep $t$ (dimension $d$)
• $W_h$: hidden-to-hidden weight matrix (shape $d \times d$)
• $h_{t-1}$: previous hidden state (dimension $d$)
• $W_x$: input-to-hidden weight matrix (shape $d \times d$, assuming input dimension matches $d$)
• $x_t$: input at timestep $t$
• $\sigma$: activation function (e.g., tanh)

The computational cost per timestep is:

• Matrix-vector multiplication $W_h h_{t-1}$: $O(d^2)$ operations
• Matrix-vector multiplication $W_x x_t$: $O(d^2)$ operations
• Activation function: $O(d)$ operations

Total per step: $O(d^2)$. For $n$ tokens: $O(nd^2)$.

RNN complexity is linear in sequence length and quadratic in hidden dimension. This is a notable contrast with attention: the RNN pays its quadratic cost in the model dimension, while attention pays its quadratic cost in the sequence length. The choice of architecture is essentially a choice about which resource you can afford to spend quadratically.

Summarizing the complexity of each architecture:

• Attention: $O(n^2 d)$
• RNN: $O(nd^2)$

where $n$ is sequence length and $d$ is the hidden/model dimension.

The key insight is that these two complexities share the same functional form with $n$ and $d$ swapped. Attention is quadratic in $n$, linear in $d$. RNN is linear in $n$, quadratic in $d$. This symmetry is not coincidental: it reflects the fundamental trade-off between sequential processing (which pays a fixed cost per step but must be sequential) and parallel processing (which can run in parallel but must examine all pairs).

To find when these costs are equal, we set $n^2 d = nd^2$ and solve for $n$:

Dividing both sides by $nd$ (assuming $n, d > 0$):

This crossover point has a clear interpretation: when sequence length exceeds model dimension ($n > d$), attention becomes more expensive. When model dimension exceeds sequence length ($n < d$), RNN becomes more expensive. In practice, modern language models have dimensions of 512 to 4096, meaning that attention is more expensive than RNN for any sequence longer than a few hundred to a few thousand tokens. Since many practical tasks involve sequences longer than that, this crossover is reached regularly in real workloads.

The crossover behavior has practical implications. For short sequences (a few hundred tokens), attention's overhead is minimal and often smaller than the equivalent RNN. For long documents, books, or conversation histories spanning thousands of tokens, the quadratic cost becomes the dominant bottleneck. This explains the historical dominance of transformers for classification and short generation tasks, alongside early proposals to handle long sequences through hierarchical chunking: run attention on small windows, then run attention again over the chunk summaries. The quadratic cost was "tamed" rather than solved until more principled efficient attention methods arrived.

Why use attention despite its higher cost at long sequences? The answer lies in path length, a concept that quantifies how "far" information must travel to flow from one part of a sequence to another. In an RNN, information from token $i$ to token $j$ must traverse $|j - i|$ sequential steps, each involving a learned transformation that can potentially lose or distort information. In attention, any two tokens connect in a single step, with no intermediaries.

Think of it as the difference between a telephone game and a conference call. In the telephone game (RNN), a message passes through a chain of people, each one rephrasing it before passing it on. After 50 iterations, the message may be unrecognizable. In a conference call (attention), everyone hears the original speaker directly, regardless of how far apart they are. The conference call is more expensive to organize for large groups, but it preserves message fidelity perfectly.

The "Efficiency" column (path improvement divided by compute ratio) quantifies the value proposition of attention. At $n = 128$, we pay only 0.25x the compute of an RNN while gaining 63x shorter average paths, yielding an efficiency of 252. At $n = 512$ (the crossover point), we pay 1x compute for 255x path improvement. At $n = 2048$, we pay 4x more compute but get 1023x shorter paths. Notice that efficiency remains nearly constant around $d/2 = 256$. This reveals an important insight: as sequence length grows, both the path improvement and the compute penalty scale proportionally with $n$. Attention's value proposition stays roughly constant regardless of sequence length. The short path lengths are always worth the extra compute.

This constancy is a powerful argument for attention. One might worry that at very long sequences, the quadratic overhead makes the mechanism unjustifiable. But the analysis shows otherwise: longer sequences also mean proportionally longer average RNN paths, so the benefit of short connections grows in proportion to the cost. The relative advantage of direct connections remains stable even as absolute costs grow. This is why the field did not abandon attention as sequences grew longer; instead, it found ways to make attention cheaper.

Given the quadratic complexity, what are the practical limits for attention-based models? The answer depends on hardware constraints, training budget, and inference requirements. This section translates the abstract complexity formulas into concrete numbers for specific GPU configurations and model architectures, giving you the tools to estimate whether a particular context length is feasible for a given setup.

Understanding these limits matters for both research and deployment. When designing a new model, you need to know whether your intended context length fits within your training budget. When deploying an existing model, you need to predict how latency and memory usage will scale with input length. When evaluating a new paper's claims about long-context capability, you need to understand what hardware was required and whether those results are reproducible at your scale.

The two primary constraints are memory (does the computation fit in GPU memory?) and time (is the computation fast enough for the application?). These constraints interact in interesting ways: memory-efficient algorithms like FlashAttention can reduce peak memory usage, which allows longer sequences, but they may have different compute patterns than naive attention and do not always achieve the same throughput. Optimizing for memory and optimizing for speed are related but distinct engineering goals.

Modern GPUs have 16GB to 80GB of high-bandwidth memory. With fp16 precision (2 bytes per element), the attention matrix for a single layer with 12 heads at sequence length 8192 requires:

where:

• $M$: memory in bytes
• $h = 12$: number of attention heads
• $n = 8192$: sequence length
• $b = 2$: bytes per element (fp16)

For a 12-layer model, that's approximately 18GB just for attention matrices, before accounting for model weights, other activations, or gradients. Training requires additional memory for optimizer states (often 2x the model size for Adam) and gradient accumulation. In practice, the 8192-token context would be infeasible to train on a single GPU with this configuration without memory-reduction techniques.

The memory calculation reveals why the 2048-token context that was standard in GPT-3 represented a real constraint. At 2048 tokens, the same 12-head, 12-layer model requires only about 1.1GB for attention matrices, comfortably fitting on most GPUs alongside the model weights and optimizer states. At 4096 tokens this grows to 4.5GB, at 8192 to 18GB, at 16384 to 72GB. The quadratic scaling is starkly visible in these numbers: each doubling of context length requires four times as much memory for the attention component alone.

These estimates assume 70% of GPU memory is available for attention matrices (the remaining 30% accounts for model weights and other overhead). An RTX 3090 with 24GB can handle approximately 27K tokens, while an A100 80GB extends this to around 50K tokens. These numbers represent theoretical upper bounds for a single sample with batch size 1. In practice, larger batch sizes for training efficiency, gradient storage for backpropagation, and optimizer states further reduce these limits.

Production systems address these constraints through several techniques working in combination. Gradient checkpointing trades computation for memory by discarding intermediate activations during the forward pass and recomputing them during backpropagation. FlashAttention restructures the computation to avoid materializing the full attention matrix in off-chip memory. Model parallelism distributes computation across multiple GPUs, so the effective memory available for the attention matrices scales with the number of devices. Together, these techniques can extend practical context lengths by an order of magnitude or more beyond the naive estimates, at the cost of engineering complexity and, in some cases, increased training time.

Beyond memory, compute time imposes practical limits. Processing long sequences is slow, and the slowness compounds in important ways during both training and inference. During training, each batch of long sequences requires proportionally more computation, which means more GPU-hours per training step. During autoregressive inference (where the model generates one token at a time), the situation is particularly challenging: each new token is generated by running a full forward pass over the entire accumulated context, so generating the $k$-th token requires a context of length $k$. This means that generating a 10,000-token response is not just 10 times more expensive than a 1,000-token response: it involves 10,000 forward passes each processing an increasingly long context, creating a super-linear increase in total generation time.

The timing curve shows why context length is such a hot topic in LLM development. Crossing the 100ms threshold makes interactive applications sluggish. Crossing 1 second makes them impractical for real-time use.

The combination of quadratic time and space complexity creates what is known as the attention bottleneck. As we push for longer context windows, attention becomes the dominant cost, often exceeding all other components combined. This section makes that claim precise by computing the actual FLOP distribution across transformer components at various sequence lengths.

Understanding this distribution is important because it reveals where optimization effort should be directed. At short sequences, optimizing attention provides minimal benefit; the feed-forward network is the bottleneck and any attention speedup is drowned out. At long sequences, the situation reverses completely: you could make the feed-forward network infinitely fast and still be limited by attention's quadratic cost. Knowing which regime you are in determines whether efficient attention variants are worth the implementation complexity.

The crossover happens gradually. Think of a transformer layer as a budget of operations. At short sequences, the $n^2 d$ attention cost is small relative to the $n d^2$ cost of two linear layers in the feed-forward network. As sequence length grows, the attention cost grows quadratically while the feed-forward cost grows only linearly. At some crossover sequence length, attention overtakes the feed-forward as the dominant component, and beyond that point, attention efficiency is what matters most.

This visualization shows the attention bottleneck in action. The red region (attention core) expands as sequence length grows, squeezing out other components. This is why efficient attention mechanisms are such an active research area. Notice that the transition is not sharp: even at 4096 tokens, feed-forward operations still account for a substantial fraction of computation. But the trend is clear, and at 8192 tokens and beyond, attention has become the defining cost.

The quadratic complexity of standard attention has motivated an entire subfield of research into more efficient alternatives. Understanding these options is important for two reasons: it shows you what trade-offs are available when quadratic attention becomes prohibitive, and it illustrates the creative approaches researchers have taken to break the $n^2$ barrier without abandoning the core insight that all-pairs interaction is useful.

The key challenge in designing efficient attention is that you cannot simply compute fewer interactions without risking the loss of important long-range dependencies. Different variants make different assumptions about which interactions are dispensable. Linear attention methods assume that the interaction pattern can be approximated using lower-rank representations. Sparse attention methods assume that each token only needs to attend to a small subset of positions. Local attention methods assume that most relevant context is nearby, with occasional global dependencies handled by special mechanisms. Each assumption is correct in some settings and wrong in others.

Think of the trade-off this way: standard attention is like an exhaustive library search that checks every single book for relevance. It never misses anything, but it is expensive. Efficient attention variants are like using an index, relying on subject headings, or trusting that nearby shelves are most relevant. Each strategy can dramatically reduce the search effort, at the risk of occasionally missing an important reference that the full search would have found.

While a detailed treatment of each variant deserves its own chapter, this comparison puts the complexity analysis in context and helps you evaluate which variant is appropriate for a given task.

Several methods approximate attention with linear complexity by avoiding the explicit $n \times n$ matrix. The core insight is that softmax attention can be written as a similarity function between queries and keys, and certain similarity functions can be decomposed into feature maps that allow the computation to be reordered. Instead of computing $(QK^T)V$ (which requires the $n \times n$ intermediate), these methods compute $Q(K^TV)$, where the parenthesized term has shape $d \times d$ rather than $n \times n$.

• Linformer: Projects keys and values to a fixed low-dimensional space before computing attention. If keys and values are projected to $k$ dimensions where $k \ll n$, the attention matrix becomes $n \times k$ rather than $n \times n$, achieving $O(nk)$ complexity with $k$ as a fixed hyperparameter.
• Performer: Uses random feature maps to approximate softmax attention in $O(n)$ time. The random features are chosen so that their inner product approximates the exponential kernel that softmax attention implicitly computes.
• Linear Transformers: Replace softmax with kernel functions (such as the ReLU feature map) that allow associative computation. Because the kernel decomposes as a product of query and key features, the computation can be reordered to avoid the $n \times n$ matrix.

These methods trade accuracy for speed, often working well in practice despite theoretical approximation. The main limitation is that removing the softmax normalization can destabilize training, and the approximation quality degrades for queries that are far from the key distribution. In practice, linear attention methods often underperform full attention on tasks requiring precise long-range matching, while performing comparably on tasks where approximate retrieval is sufficient.

Instead of attending to all positions, sparse methods attend to a carefully chosen subset. The key question is which subset to choose: a random subset, a structured subset based on proximity, or a learned subset based on content. Different choices lead to different architectural properties.

• Longformer: Combines local windowed attention (each token attends to nearby tokens within a window) with global attention on special tokens like [CLS]. The global tokens can attend to and be attended by all positions. This provides pathways for long-range information while keeping most attention local.
• BigBird: Uses a combination of random and window attention with global patterns. The theoretical motivation is that this combination is sufficient to preserve the expressive power of full attention for most practical tasks, at a fraction of the cost.
• Sparse Transformers: Learn which positions to attend to, adapting the attention pattern to the data rather than fixing it in advance. This is more powerful but introduces training complexity.

Sparse attention reduces complexity to $O(n \cdot k)$, where:

• $n$: sequence length
• $k$: number of positions each token attends to (typically $k \ll n$)

For example, with a local window of 256 tokens, $k = 256$ regardless of sequence length, making the complexity effectively linear in $n$. The key assumption behind sparse attention is that most relevant context for any given token is local, with occasional non-local dependencies that can be handled through global token mechanisms or random connections. This assumption holds well for natural language, where adjacent sentences are usually more relevant than distant ones, but may fail for tasks requiring systematic long-range reasoning such as mathematical proofs or algorithmic reasoning over large structures.

A third class of approaches does not approximate the attention function at all, but instead restructures the computation to be more hardware-efficient. These methods compute exactly the same attention as the standard algorithm but do so in a way that reduces the amount of data moved between different memory levels on the GPU.

• FlashAttention: Reorders operations to minimize memory transfers between GPU high-bandwidth memory (HBM) and the faster on-chip SRAM. Standard attention writes the $n \times n$ attention matrix to HBM and reads it back for the output computation. FlashAttention instead tiles the computation so that each block of the attention matrix is computed, used for the corresponding output block, and discarded without ever writing to HBM. The result is identical to full attention mathematically, but achieves 2 to 4x speedup due to reduced memory bandwidth, with memory usage $O(n)$ rather than $O(n^2)$.
• KV Caching: During autoregressive generation, caches key-value pairs from all previous tokens to avoid recomputing them at each step. The cache grows linearly with the number of generated tokens and must be stored in memory for the duration of generation. For long outputs, KV cache management (including eviction strategies when the cache exceeds memory) becomes a significant engineering challenge.
• Gradient Checkpointing: Trades computation for memory during training by discarding intermediate activations after the forward pass and recomputing them from saved checkpoints during backpropagation. This reduces activation memory from $O(n^2 L)$ (proportional to all layers and sequence length squared) to roughly $O(n^2 \sqrt{L})$ with some computational overhead.

The quadratic complexity of attention is both its greatest strength and most significant limitation. The all-pairs computation enables transformers to capture any dependency regardless of distance, but it also creates hard limits on context length that no amount of hardware can fully overcome. This section synthesizes the practical implications of everything we have analyzed and discusses the broader impact on how language model systems are designed.

For practitioners, understanding these complexity bounds is essential for making informed architecture decisions. When processing short sequences (a few hundred tokens), attention overhead is negligible compared to feed-forward layers. In this regime, you can use standard attention without concern and should focus optimization efforts elsewhere (model quantization, batching strategy, caching). However, when context length grows into the thousands or tens of thousands, attention becomes the dominant cost. You need to consider sparse attention variants, linear approximations, or hierarchical processing strategies. The crossover point depends on your model size, but for typical configurations, it occurs around 512 to 1024 tokens.

Memory constraints often bite before compute constraints do. During training, storing attention matrices for backpropagation requires $O(n^2)$ memory per layer. This quadratic memory scaling is why long-context training requires techniques like gradient checkpointing (trading compute for memory), FlashAttention (reordering operations to reduce memory), or model parallelism (distributing across multiple GPUs). The memory bottleneck also affects inference, especially when serving many concurrent requests with long contexts. A server handling 100 simultaneous requests each with 32K tokens of context must maintain 100 separate KV caches, each potentially tens of gigabytes in size. At scale, the memory management of attention caches becomes a primary concern for inference infrastructure engineers.

The complexity analysis also explains why efficient attention is such an active research area. Linearizing attention, sparsifying attention patterns, and approximating attention with lower-rank structures are all attempts to break the quadratic barrier while preserving the benefits of all-pairs interaction. These techniques have enabled models with 100K+ token context windows, but they often involve trade-offs in accuracy or increased implementation complexity. Understanding when these trade-offs are acceptable requires understanding the underlying complexity.

Quadratic scaling does not prevent building very capable models. GPT-4 and systems such as Gemini or Claude all use standard or near-standard attention with large context windows. The cost is paid through massive compute infrastructure, carefully optimized implementations (especially FlashAttention), and systems engineering that manages memory efficiently. The quadratic cost is a hard physical constraint, but it is a constraint that engineering can work around at sufficient scale. What it does mean is that every doubling of context length requires a four-fold increase in attention compute and memory, making each step toward longer context exponentially more expensive than the last.

Attention's quadratic complexity is a fundamental characteristic that shapes how we build and use transformer models. In this chapter, we analyzed this complexity from multiple angles, built precise formulas for estimating real-world costs, compared attention to recurrent alternatives, and surveyed a range of efficient attention methods.

Key takeaways:

• Time complexity: Standard self-attention requires $O(n^2 d)$ operations, where $n$ is sequence length and $d$ is model dimension. The $n^2$ term means doubling sequence length quadruples computation. This is not an approximation or a worst-case bound: it is the exact cost of the all-pairs interaction that defines the mechanism.

• Memory complexity: Storing attention matrices requires $O(h \cdot n^2)$ memory, where $h$ is the number of heads. This quadratic memory scaling often becomes the limiting factor before compute does. Doubling context length quadruples memory for attention matrices, which is why GPU memory capacity is a central constraint in long-context systems.

• Three-stage decomposition: The cost breaks down as score computation ($n^2 d_k$ operations), softmax normalization ($3n^2$ operations), and output aggregation ($n^2 d_v$ operations). The softmax is negligible; the two matrix multiplications dominate.

• Crossover with RNN: Setting $n^2 d = nd^2$ shows that attention is cheaper than RNN when $n < d$, but more expensive when $n > d$. For typical model dimensions (512 to 4096), attention becomes more expensive beyond a few hundred tokens. Despite this, attention is preferred because path lengths are $O(1)$ rather than $O(n)$, making long-range dependencies much easier to learn.

• Practical limits: GPU memory and compute time impose hard constraints on context length. Even with 80GB GPUs, sequence lengths beyond tens of thousands of tokens require specialized techniques. The memory bottleneck typically arrives before the compute bottleneck at realistic batch sizes.

• The attention bottleneck: As sequence length grows, attention dominates transformer computation. At 256 tokens, attention is only 5% of layer FLOPs. At 4096 tokens, it approaches 45%. Beyond 8192 tokens, attention is the primary cost component in each transformer layer.

• Efficient alternatives: Linear attention, sparse attention, and memory-efficient implementations (especially FlashAttention) can reduce effective complexity from $O(n^2)$ to $O(n)$ or $O(n \cdot k)$, where $k$ is the number of attended positions. FlashAttention achieves the same result as full attention with less memory by restructuring computation to minimize data movement between memory tiers.

Understanding these complexity characteristics is essential for choosing appropriate architectures, estimating computational requirements, and knowing when to apply optimization techniques. The quadratic wall is real, but the right tools and understanding can help keep it manageable. The progression from 512-token BERT to million-token Gemini reflects hardware improvements and algorithms such as FlashAttention, supported by engineering that keeps the $n^2$ term manageable without sacrificing the expressive power that makes attention valuable in the first place.

When analyzing or estimating attention complexity, several parameters directly impact computational and memory requirements. Understanding how each one affects cost allows you to make informed choices when designing or selecting models.

• n (sequence length): The number of tokens in the input sequence. This is the most critical parameter since complexity scales quadratically with it. Typical values range from 512 to 128K+ in modern models. Because of the quadratic relationship, changes to this parameter have a much larger effect on total cost than changes to any other. Changing $n$ from 2K to 8K quadruples attention cost; no other parameter has this multiplier effect.

• d (model dimension): The embedding dimension of the model. Common values include 768 (GPT-2 Small), 1024 (GPT-2 Medium), 4096 (LLaMA 7B), and larger for bigger models. Complexity scales linearly with this parameter. Making models wider is relatively cheap compared to making them longer-context.

• h (number of heads): The number of attention heads. Each head operates on $d/h$ dimensions. More heads mean more parallel attention patterns but also more attention matrices to store. Critically, the total FLOPs for multi-head attention are the same as for a single head with the full dimension, because the reduction in per-head dimension exactly offsets the increase in number of heads. However, memory scales with $h$ because all $h$ attention matrices must be stored simultaneously.

• L (number of layers): Total transformer layers. Memory and compute scale linearly with layer count, so a 24-layer model requires twice the resources of a 12-layer model. Adding layers is one of the "cheap" ways to increase model capacity: it costs linearly and does not interact with the quadratic sequence-length term.

• dtype_bytes: Precision of floating-point representation. fp32 uses 4 bytes, fp16/bf16 use 2 bytes. Half precision halves memory requirements and often doubles throughput on modern GPUs. Moving from fp32 to bf16 is one of the simplest ways to double your effective context capacity within a fixed memory budget.

• batch_size: Number of sequences processed simultaneously. Memory scales linearly with batch size, often requiring batch size reduction for long sequences. At very long context lengths, batch sizes of 1 or 2 are common in production, meaning the full GPU memory is devoted to a single request's attention matrices and KV cache.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about attention complexity and efficient alternatives.