Quadratic Attention Bottleneck

Transformers have revolutionized natural language processing, powering everything from chatbots to code assistants to scientific discovery tools. At the heart of their success lies self-attention: a mechanism that allows every token to directly interact with every other token in the same sequence. This all-pairs computation is both the transformer's greatest strength and its Achilles' heel. As sequence length grows, the computational and memory demands explode quadratically, creating a fundamental barrier to processing long documents, extended conversations, and book-length texts.

Think of self-attention as a room full of people where everyone must personally introduce themselves to everyone else. In a room of 10 people, that's 100 handshakes. Double the room size to 20 people and you don't get 200 handshakes. You get 400. Double it again to 40 people and you're at 1,600 handshakes. The count follows the square of the room size, and it grows far faster than intuition suggests. Self-attention has this exact property: the number of token interactions is not $n$ (linear) or even $2n$, but $n^2$.

This quadratic relationship was an acceptable trade-off during the early transformer era. Most NLP tasks operated on short texts: single sentences, short paragraphs, or brief documents. BERT processed sequences of at most 512 tokens, and GPT-2 handled 1,024. At those lengths, the quadratic cost was manageable. The trouble began when practitioners wanted more: longer prompts, full-document summarization, cross-reference reasoning over entire codebases, or conversational history spanning dozens of turns. Suddenly, the quadratic bottleneck was no longer a theoretical concern but a hard engineering wall.

The key insight is that the problem extends beyond raw computational speed. Even if you had an infinitely fast processor, the quadratic memory requirement would stop you first. Attention matrices must be stored in GPU memory, and GPU memory is finite and expensive. A sequence of 32,768 tokens at standard model sizes requires more memory for attention alone than exists in any single GPU on the market. You cannot simply wait longer for the computation to finish when the data does not fit in memory.

In this chapter, we analyze why this quadratic bottleneck exists, quantify its impact on real systems, and visualize how quickly resources become exhausted. We trace the cost through every stage of the attention computation: from the initial score matrix construction through softmax normalization to the final weighted aggregation. We compare memory and compute requirements across different model configurations and sequence lengths, and we ground the abstract scaling laws in concrete GPU memory limits. Understanding this limitation sets the stage for the efficient attention variants covered in subsequent chapters, where we will see how researchers have found clever ways to break, approximate, or work around the $n^2$ barrier.

Self-attention computes relationships between every pair of tokens in a sequence. For a sequence of $n$ tokens, this means $n^2$ pairwise interactions. This is the defining structural feature of attention, and it is the root cause of every scaling challenge discussed in this chapter.

To understand why all pairs are necessary, consider what attention is trying to accomplish. When reading the sentence "The trophy didn't fit in the suitcase because it was too big," a model needs to determine that "it" refers to "the trophy," not "the suitcase." To resolve this correctly, the word "it" must simultaneously consider "trophy," "suitcase," and "big" and compare their relevance. Attention provides exactly this capability: every token can look at every other token and decide how much weight to give each one. Restricting this to a subset of tokens would risk missing the very long-range dependencies that make attention powerful.

The complete attention formula captures this all-pairs comparison in matrix form. To compute attention for a sequence of $n$ tokens with representations of dimension $d_k$, we first project each token into QKV vectors, then compute:

where:

• $Q \in \mathbb{R}^{n \times d_k}$: the query matrix, with one row per token representing "what this token is looking for"
• $K \in \mathbb{R}^{n \times d_k}$: the key matrix, with one row per token representing "what this token contains"
• $V \in \mathbb{R}^{n \times d_v}$: the value matrix, with one row per token representing the information to aggregate
• $d_k$: the dimension of queries and keys, used as a scaling factor
• $n$: the sequence length (number of tokens)

The critical operation is $QK^T$, which produces an $n \times n$ attention score matrix. Every element $(i, j)$ in this matrix represents how much token $i$ should attend to token $j$. Computing all $n^2$ entries is what gives attention its power: any token can directly influence any other, regardless of distance. But this same property creates the quadratic scaling problem.

Consider the contrast with sequential processing. In a recurrent neural network, information from token 1 must propagate through tokens 2, 3, 4, and so on to reach token 100. In attention, token 1 directly connects to token 100 in a single step. This short path length is why transformers excel at capturing long-range dependencies. The price is computing all pairwise interactions up front, and that price grows quadratically.

Notice that there is no mathematical shortcut here. The score matrix entry at position $(i, j)$ requires knowledge of both token $i$'s query and token $j$'s key. Until you compute all $n^2$ scores, you cannot determine which tokens attend to which. Later in this part of the book, we will explore approximations that avoid computing the full matrix, but they do so at the cost of either accuracy or certain types of dependencies.

The first panel shows the raw explosion in pair count, rising from near zero at short sequences to over 16 million at 4,096 tokens. The second panel, using logarithmic scales on both axes, reveals the underlying structure: a straight line with slope 2, confirming the $n^2$ relationship. Each doubling of sequence length produces exactly a 4x increase in pairs, marked along the curve.

The log-log view is particularly instructive because it turns the quadratic relationship into something visually linear, making the constant growth factor visible at every step. Any time you see a log-log plot produce a straight line with slope 2, you are looking at quadratic scaling.

Memory is often the first constraint that prevents you from extending sequence lengths, and the source of that constraint is the attention score matrix. To understand why, consider what must be stored during a single forward pass of a transformer with self-attention.

For every attention head, the model must compute and store an $n \times n$ matrix of attention scores before applying softmax. This matrix is not just used once: it drives the final weighted aggregation of value vectors, and during training it must be retained for the backward pass so that gradients can flow back through the softmax operation. The result is that the $n \times n$ attention matrix lives in GPU memory for the entire duration of the forward and backward pass, consuming resources proportional to the square of the sequence length.

Think of the attention matrix as a large lookup table. For a sequence of 1,024 tokens, the table has 1,024 rows and 1,024 columns, totaling roughly one million entries. For 8,192 tokens, the table grows to 67 million entries. For 32,768 tokens, it reaches one billion entries. At two bytes per entry (fp16), that single table consumes roughly 2 gigabytes for the 32K case, and that's just one head of one layer.

The total memory required to store attention matrices across all heads and all layers in a transformer can be expressed concisely. For a model with $h$ attention heads and $L$ layers, with each layer computing an $n \times n$ attention matrix per head at precision $b$ bytes per element:

where:

• $M_{\text{attn}}$: total memory in bytes for all attention matrices
• $h$: number of attention heads (each head computes an independent $n \times n$ attention pattern)
• $n$: sequence length (number of tokens)
• $n^2$: the number of entries in each attention matrix, one score per query-key pair
• $b$: bytes per element (4 for fp32, 2 for fp16/bf16, often 2 in modern practice)
• $L$: number of transformer layers (each layer adds another full set of attention matrices)

Notice that this formula has $n^2$ as its only non-linear term. Every other factor ($h$, $b$, $L$) is a constant that scales linearly with model size. The sequence length $n$ is unique in appearing squared, which is why attention memory grows so much faster than model size as context lengths increase.

Let's make this concrete with a real calculation. Consider a LLaMA 7B-style model with 32 attention heads, 32 layers, and fp16 precision ($b = 2$ bytes). At a sequence length of 8,192 tokens:

Working through the calculation step by step:

This is before counting model weights, activations, gradients, or optimizer states. A LLaMA 7B model at 8,192 tokens already needs 128 GB for attention matrices alone, far exceeding the 80 GB capacity of an H100 GPU. This is the memory wall in concrete form.

The plot shows that even the smallest model configuration exceeds a 24 GB GPU around 16K tokens, and an 80 GB GPU around 32K tokens. Larger models hit these limits much sooner. This memory wall is often the first constraint encountered when extending context length, and it explains why the earliest long-context research focused on memory reduction rather than computational speedup. Saving memory, as FlashAttention famously demonstrated, can be a more impactful contribution than saving compute.

We have seen that attention requires storing an $n \times n$ matrix of weights. But how much computation does it take to produce those weights and use them? Understanding the computational cost helps us predict training times, estimate inference latency, and appreciate why efficient attention variants are so valuable.

The answer turns out to be $O(n^2 d)$ floating-point operations per attention layer, where $d$ is the model dimension. To see where this comes from, let's trace through exactly what happens when attention runs, quantifying each operation precisely.

Before diving into the math, consider what attention needs to accomplish for each token in the sequence:

1. Compare this token to every other token to determine relevance scores
2. Normalize those scores into a probability distribution
3. Blend information from all tokens according to those probabilities

For a sequence of $n$ tokens, step 1 alone requires $n$ comparisons per token, and we have $n$ tokens, giving us $n \times n = n^2$ comparisons. This is the fundamental source of quadratic scaling: the all-pairs comparison cannot be avoided in standard attention. Steps 2 and 3 must process the results of step 1, so they also touch $n^2$ entries.

Now let's quantify each step precisely and see how the costs add up.

The first operation computes how strongly each query should attend to each key. Mathematically, this is the matrix multiplication $QK^T$, where $Q$ contains all query vectors (one per token) and $K$ contains all key vectors.

When we multiply a matrix of shape $(n \times d_k)$ by a transposed matrix of shape $(d_k \times n)$, we get an $(n \times n)$ output. Each entry in this output matrix is a dot product between one query and one key, requiring $d_k$ multiplications and $d_k - 1$ additions. With $n^2$ such entries, the total operation count for this stage is:

where:

• $n^2$: the number of query-key pairs (one score per pair)
• $d_k$: the dimension of each query and key vector (typically $d / h$ for $h$ heads)
• $2$: accounts for both multiplications and additions in each dot product (counted as a single fused multiply-add operation on modern hardware)

The $n^2$ appears because every token must be compared against every other token. There is no shortcut here: we do not know which pairs will have high attention until we compute all the scores. This is the irreducible cost of the all-pairs comparison.

Raw dot products can be any real number, positive or negative, and their magnitudes depend on the model's learned parameters. To use them as weights in a weighted average, we need to convert each row of scores into a probability distribution that sums to 1. The softmax function accomplishes this, converting each row of scores into non-negative weights that sum to exactly 1.

For a row of $n$ attention scores $s_1, s_2, \ldots, s_n$, softmax computes:

where:

• $s_i$: the raw dot product score for the $i$-th position in the row
• $e^{s_i / \sqrt{d_k}}$: the exponential of the scaled score. This keeps all weights are positive
• $\sum_{j=1}^{n} e^{s_j / \sqrt{d_k}}$: the normalizing constant, summing over all positions in the row
• $\sqrt{d_k}$: the scaling factor that prevents dot products from growing too large in magnitude, which would push softmax into regions of near-zero gradient

The $\sqrt{d_k}$ scaling is a detail from the original Transformer paper, motivated by the observation that without it, dot products grow in magnitude with $d_k$, pushing gradients to near zero during training. Scaling by $\sqrt{d_k}$ keeps the scores in a range where softmax gradients remain healthy.

For each of the $n$ rows in the attention matrix, softmax requires exponentiating $n$ scores, summing those $n$ exponentials, and dividing each of the $n$ exponentials by the sum. This contributes roughly $5n$ operations per row. With $n$ rows:

While still quadratic in $n$, the softmax cost lacks the $d_k$ factor, making it smaller than score computation when $d_k$ is large. For typical transformers where $d_k = 64$ to $128$, softmax contributes less than 10% of the total attention FLOPs. It is not negligible, but it is not the dominant term.

The final step uses the normalized attention weights to compute a weighted combination of value vectors. Each token's output is a blend of all tokens' values, weighted by attention. In matrix form, this is:

where the left factor is the $(n \times n)$ attention weight matrix and the right factor $V$ is the $(n \times d_v)$ value matrix.

This is another matrix multiplication: the $(n \times n)$ attention weights multiplied by the $(n \times d_v)$ value matrix produces an $(n \times d_v)$ output. Each of the $n \times d_v$ output elements requires summing across $n$ weighted values:

where:

• $n^2$: the number of weight-value multiplications (every output position must aggregate from all $n$ positions)
• $d_v$: the dimension of each value vector (typically equal to $d_k$ in standard transformers)
• $2$: multiply-add pairs as before

This matches the cost of score computation exactly when $d_v = d_k$. We have encountered two expensive $O(n^2 d)$ operations, and they dominate the total cost of attention.

The visualization confirms our analysis: score computation and output computation each consume roughly half the total FLOPs (about 49.8% each), while softmax contributes less than 0.4%. The two matrix multiplications involving the $n \times n$ attention matrix dominate entirely. Any optimization that targets the softmax step alone will have negligible impact on the overall compute budget.

Combining all three stages, the total computational cost of self-attention for a single head is:

where:

• $n$: sequence length (number of tokens)
• $d_k$: dimension of query and key vectors (typically $d / h$, where $h$ is the number of heads)
• $d_v$: dimension of value vectors (typically equal to $d_k$)
• $d$: model dimension (the full embedding size before splitting into heads)
• $h$: number of attention heads

The simplification to $O(n^2 d)$ holds because $d_k$ and $d_v$ are both proportional to $d$. In standard transformers, each head operates on $d/h$ dimensions, and since we sum across all heads, the total work scales with the full model dimension $d$.

The formula $O(n^2 d)$ reveals an important asymmetry in how the two factors affect complexity:

• Doubling $n$ quadruples the computation because $n$ appears squared
• Doubling $d$ only doubles the computation because $d$ appears linearly

This asymmetry determines which factor becomes the bottleneck. For a model with $d = 768$ processing $n = 4,096$ tokens, the $n^2 = 16{,}777{,}216$ factor dwarfs the $d = 768$ factor by a ratio of over 20,000 to 1. The quadratic term completely dominates, which is why sequence length is the bottleneck rather than model size when processing long documents.

The practical consequence is that scaling up the model (increasing $d$) is far less damaging to inference speed than scaling up the context (increasing $n$). A model twice as wide is only twice as slow. A model with twice the context length is four times as slow. This is why researchers are far more willing to increase model dimension than context length when staying within a compute budget.

Let's make this concrete by computing the actual FLOPs for a GPT-2 style model with $d = 768$ across a range of sequence lengths:

The numbers tell the story of quadratic growth. At 512 tokens, a single attention layer performs about 1.6 billion operations, which modern GPUs handle in microseconds. At 2,048 tokens (4x longer), the count grows to roughly 26 billion operations (16x more, confirming the quadratic relationship). By 32,768 tokens, we are approaching 7 trillion operations per layer.

For a complete transformer, multiply these numbers by the layer count. A 12-layer GPT-2 at 4,096 tokens performs over 1.2 trillion attention operations. During training, backpropagation roughly triples this cost (forward pass, backward for computing gradients, backward for applying updates). The computational demands compound rapidly, and attention becomes the dominant bottleneck for long sequences.

In practice, the FLOPs budget for a long-context model is not simply "how long will this take on a single GPU." It also drives decisions about parallelism strategies, batch sizes, gradient checkpointing, and mixed-precision training. Every engineering decision that reduces the effective $n^2$ cost has compounding effects throughout the training pipeline.

The $n \times n$ attention matrix lies at the center of the bottleneck. Visualizing its structure helps build intuition for why it is both powerful and expensive, and why efficient alternatives that avoid materializing the full matrix are so impactful.

The attention matrix is not a random array of numbers. It has structure: tokens tend to attend strongly to nearby tokens (local context), to semantically related tokens regardless of distance (content-based attention), and to certain special tokens like sentence boundaries or separator tokens (global attention). This structure is precisely what efficient attention methods exploit. If the matrix were truly dense and unstructured, there would be no way to approximate it accurately without computing all $n^2$ entries.

As the sequence length grows, the attention matrix balloons in size. At $n=16$, the matrix is compact and easy to visualize. At $n=256$, individual cells become indistinguishable. At $n=8192$ (a common context length for modern LLMs), the matrix would contain over 67 million entries, impossible to render at a reasonable resolution.

The structured patterns visible in these matrices hint at why sparse attention methods work. Much of the attention mass concentrates on the diagonal (local context), certain global tokens, and specific positions. The full $n^2$ matrix contains substantial redundancy that efficient methods can exploit. A model that attends only within a local window of 256 tokens and to a small set of global tokens can capture most of the information in the full attention matrix at a fraction of the cost.

Notice also that the patterns become denser and more uniform as $n$ increases. This is not accidental: longer sequences tend to have more distributed attention patterns because there are more positions competing for weight. This observation has practical consequences for efficiency methods that rely on sparsity: they work better when attention is naturally sparse, which is more likely at short to medium sequence lengths than at very long ones.

Given the quadratic scaling, what are the practical limits for standard attention? The answer depends on hardware constraints and whether you are training or doing inference, and the distinction between these two regimes is important.

During inference, you need to store only the current attention matrix (and possibly key-value caches for fast autoregressive generation). During training, you must also store the attention matrices for every layer simultaneously, because the backward pass needs them to compute gradients. This difference means that training is far more memory-constrained than inference, and the practical sequence length limit during training can be several times lower than during inference.

The key constraint is whether the entire computation graph fits after accounting for every memory consumer, including the attention matrices. Model weights typically occupy a fixed amount of memory regardless of sequence length. Activations from feed-forward layers and residual connections scale linearly with sequence length. Gradients and optimizer states (in training) scale with parameter count. Attention matrices then add the $O(n^2)$ term on top of all this.

The shaded region represents sequence lengths that exceed GPU memory for training. While compute could theoretically handle longer sequences given enough time (by reducing batch size or using gradient accumulation), memory is a hard constraint that cannot be overcome without specialized techniques. This asymmetry explains why memory-efficient attention methods like FlashAttention matter in practice: they shift the memory limit rightward without changing the compute requirements, opening up sequence lengths that were previously inaccessible.

To fully appreciate the quadratic bottleneck, we can visualize how attention costs compare to other transformer components as sequence length grows. The transformer is not only attention: it also includes feed-forward networks (FFN), layer normalization, and QKV linear projections. At short sequences, these other components can dominate. At long sequences, the quadratic attention core takes over.

The key conceptual point is that every other component in a transformer scales linearly with sequence length. The feed-forward network processes each token independently, so its cost grows as $O(nd^2)$. The QKV projection matrices each perform an $(n \times d) \times (d \times d)$ matrix multiplication, costing $O(nd^2)$. Layer normalization costs $O(nd)$. None of these touch the $n^2$ term.

This means the bottleneck is not a static property of the model architecture but a dynamic one that emerges as sequences grow. For short sequences, attention is just another cheap operation. The crossover point, where attention becomes the dominant cost, depends on the ratio of $n$ to $d$.

At short sequence lengths (128-256 tokens), the feed-forward network and projections dominate, and attention contributes less than 10% of total computation. As sequences grow, the quadratic term takes over. By 4K tokens, attention accounts for nearly half of all operations. At 16K tokens and beyond, attention consumes the vast majority of the compute budget, squeezing out everything else.

This is the attention bottleneck in visual form. Optimizing transformers for long sequences means addressing the red region in this chart. The feed-forward and projection components (orange and blue) scale linearly, which is theoretically optimal for per-token processing. It is attention's all-pairs structure that breaks linear scaling and creates the growing red region.

The crossover region around 1K-2K tokens is particularly important for practical system design. Models that process sequences mostly below this threshold can be optimized for the FFN and projection costs. Models that routinely process longer sequences must prioritize attention efficiency. This is one reason why code models and document models have driven much of the efficient attention research: they deal with long inputs by nature.

To make all of these costs concrete, let's trace a single attention layer through every operation and compute the exact memory and FLOP cost at a specific sequence length. This exercise ties together everything discussed in this chapter.

Consider a single attention layer with the following configuration, representative of one layer in a GPT-2 Medium-style model:

• Sequence length: $n = 2048$ tokens
• Model dimension: $d = 1024$
• Number of heads: $h = 16$
• Head dimension: $d_k = d / h = 64$
• Precision: fp16 (2 bytes per element)

The breakdown reveals that even for just 2,048 tokens, the attention score matrices already consume a significant portion of working memory. Now consider that a 24-layer model runs this computation 24 times simultaneously during training, and all attention matrices must be retained for the backward pass. This is where the per-layer cost scales to multi-gigabyte territory for longer sequences.

Notice also that the QKV projections, while not $O(n^2)$, are not trivial. At this sequence length, they consume more FLOPs than the attention core itself. This is the regime below the crossover point, where linear components still dominate. At 8,192 tokens (4x longer), the attention FLOPs would grow by 16x while the projection FLOPs grow by only 4x, pushing attention into dominance.

The quadratic bottleneck motivates several lines of research, each tackling the problem from a different angle. The diversity of approaches reflects the fact that there is no single solution: each method makes different trade-offs between accuracy and memory, alongside compute and implementation complexity.

Understanding these trade-offs at a high level before diving into the technical details (which the subsequent chapters cover) helps you appreciate why the field has converged on multiple solutions rather than one universal approach. The right choice depends on the application: a model summarizing academic papers has different requirements than one generating code or answering questions over a long conversational history.

Each approach involves trade-offs. Sparse attention sacrifices some global interactions that might be important for tasks requiring long-range reasoning. Linear attention may lose expressiveness on certain tasks, particularly those that benefit from the sharp selection behavior that softmax enables. Memory-efficient methods like FlashAttention require careful low-level implementation and may have higher constant factors on hardware that is not well-optimized for tiled computation. The following chapters explore each in detail, with concrete implementations that let you experiment with the trade-offs directly.

The gap between standard attention (red) and efficient variants grows dramatically at long sequences. At 64K tokens, sparse attention requires roughly 250 times fewer operations than standard attention. Linear attention, once its $O(nd^2)$ cost falls below the $O(n^2 d)$ standard cost, provides even greater savings. This difference is what enables modern long-context models to process book-length documents: without efficient attention, no amount of hardware scaling would make 100K-token contexts practical.

The quadratic bottleneck is well-understood and extensively studied, but it is worth being explicit about what it means for real systems and what it does not mean.

Standard attention is not simply slow. It is correct, in the sense that it computes the exact full attention distribution over all tokens, with no approximation. Every efficient alternative introduces either an approximation (sparse and linear attention) or a restructuring that preserves exact answers but cannot be used everywhere (FlashAttention). This distinction matters because approximate methods may perform worse on tasks that require global, long-range attention. For short to medium sequences, standard attention is the right choice: it is simple, well-understood, and produces the best possible attention distribution.

The memory constraint is also more fundamental than the compute constraint for most practical systems. Modern GPUs can handle large amounts of computation in parallel, but GPU memory is small relative to the data sizes that long-context models need to process. A batch that does not fit in memory cannot be processed at all, regardless of compute speed. This is why FlashAttention's memory savings have been more practically impactful than its speed improvements, even though both are significant.

Another limitation that often goes unmentioned is the cost of the key-value cache during autoregressive inference. When a transformer generates text one token at a time, it reuses the key and value vectors from all previous tokens to avoid recomputing them. This KV cache grows linearly with sequence length in terms of the number of entries, but the memory it consumes is still $O(n \cdot d)$ per layer, which becomes substantial at long contexts. For a 32-layer model with a 128K-token context, the KV cache alone can consume dozens of gigabytes, creating a different kind of memory pressure from the training bottleneck.

The quadratic bottleneck is a property of the standard attention formulation, not of transformers as a class. Many transformer-like architectures have been proposed that avoid the $n^2$ scaling entirely while preserving the key benefits of attention: parallel computation, direct token-to-token interaction, and expressive capacity. State space models, linear recurrences, and hybrid architectures represent active areas of research aimed at breaking the quadratic barrier at the architectural level rather than the implementation level.

The quadratic attention bottleneck is a fundamental constraint that shapes transformer design and deployment at every scale. In this chapter, we quantified the $O(n^2)$ scaling in both memory and compute, traced the cost through every stage of the attention computation, and visualized how attention costs grow to dominate transformer computation at long sequence lengths.

Key takeaways:

• The all-pairs structure drives everything. Attention computes $n^2$ interactions because every token must be compared to every other token. This is both the source of attention's power and the root cause of its scaling problems.

• Quadratic memory. Storing attention matrices requires $O(h \cdot n^2 \cdot b \cdot L)$ memory, where $h$ is the number of attention heads, $b$ is bytes per element, and $L$ is the number of layers. This often becomes the first constraint hit when extending context length.

• Quadratic compute. The attention core requires $O(n^2 d)$ operations per layer, dominated by two matrix multiplications: score computation ($QK^T$) and output aggregation ($AV$). Softmax contributes less than 1% of attention FLOPs for typical model dimensions.

• The crossover point. At short sequences, attention is a minor cost. At long sequences (roughly 1K-4K tokens for typical models), attention becomes the dominant expense and eventually consumes over 80% of transformer FLOPs.

• Memory before compute. Memory is typically the binding constraint, not compute. GPUs cannot process data that does not fit in memory, making memory-efficient attention more urgently important than compute-efficient attention.

• Practical limits. Standard attention on current GPUs is limited to roughly 16K-32K tokens for training and 50K-100K tokens for inference, depending on model size and hardware. Beyond these limits, specialized techniques are required.

• Motivation for efficiency. The quadratic bottleneck drives research into sparse attention, linear attention, and memory-efficient implementations, each trading different aspects to break the $O(n^2)$ barrier. None of these are free lunches: each introduces approximations, implementation complexity, or hardware dependencies.

Understanding this bottleneck is essential for working with long-context models and for appreciating why the efficient attention techniques covered in the following chapters are so important. The $n^2$ wall is real, but it can be scaled with the right approaches, and knowing exactly where the cost comes from is the first step toward addressing it effectively.

When analyzing attention complexity or estimating resource requirements, these parameters directly determine memory and compute costs:

• n (sequence length): The number of tokens in the input. This is the most critical parameter since both memory and compute scale with $n^2$. Typical values range from 512 (early BERT) to 128K+ (modern long-context models). Even modest increases in $n$ have dramatic effects on resource consumption.

• d (model dimension): The embedding dimension of the model. Common values include 768 (GPT-2 Small), 4,096 (LLaMA 7B), and 8,192 (larger models). Complexity scales linearly with $d$, making it far less impactful than sequence length.

• h (number of heads): The number of parallel attention heads. Each head stores an independent $n \times n$ attention matrix, so memory scales linearly with $h$. Typical values range from 12 to 128.

• L (number of layers): The depth of the transformer. Memory for attention matrices scales linearly with layer count. A 24-layer model uses twice the attention memory of a 12-layer model.

• dtype_bytes: Precision of floating-point representation. Using fp16 (2 bytes) instead of fp32 (4 bytes) halves memory requirements and often doubles throughput on modern GPUs.

• overhead_factor: When estimating maximum sequence length, this represents the fraction of GPU memory available for attention matrices after accounting for model weights and activations, plus gradients. Typical values are 0.5 for inference and 0.2 for training.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about the quadratic attention bottleneck.