Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Scaled Dot-Product Attention › Computational Complexity

Michael BrenndoerferMay 25, 20254 min read

Language AI HandbookAll chapters

Part 13 of 67Self-Attention

Chapter 92Scaled Dot-Product Attention › Computational Complexity

Reading section 10 of 15 · Computational Complexity · 4 minSection 10 of 15 · 4 min

Section 10 of 15 · 4 min read

Scaled Dot-Product Attention › Computational ComplexityOne section · Sections in this chapter10 / 15 ↓

Sections in this chapter15

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Scaled dot-product attention has a computational cost that shapes how transformers scale with sequence length. Understanding this cost motivates both current architectural choices and research into more efficient attention mechanisms. The quadratic scaling is the primary bottleneck limiting the sequence length modern transformers can process.

The dominant cost is the $QK^T$ matrix multiplication. Multiplying an $n \times d_k$ matrix by a $d_k \times n$ matrix requires $O(n^2 d_k)$ multiply-add operations. The subsequent $AV$ multiply is $O(n^2 d_v)$ . Together, the total computation is:

O(n^2 d)

where $d = \max(d_k, d_v)$ , assuming $d_k$ and $d_v$ are comparable. The quadratic factor $n^2$ means that doubling the sequence length quadruples the computation, and multiplying the sequence length by 10 increases computation by 100x.

The memory cost is also $O(n^2)$ : we must store the $n \times n$ score matrix and the $n \times n$ attention weight matrix. For typical sequence lengths of 512 or 1024 tokens with 32-bit floats, this is manageable. But for very long sequences (tens of thousands of tokens), storing $O(n^2)$ matrices becomes infeasible. A sequence of length 32,768 tokens would require a single attention matrix with over a billion entries, far exceeding available GPU memory.

In[30]:

Code

# Compute FLOPs for scaled dot-product attention
def attention_flops(n, d_k, d_v=None):
    """Approximate FLOPs for one forward pass of attention."""
    if d_v is None:
        d_v = d_k
    # QK^T: n queries x d_k x n keys -> O(n^2 * d_k) multiply-adds
    qkt_flops = 2 * n * n * d_k  # factor 2 for multiply + add
    # AV: n x n attention weights x d_v -> O(n^2 * d_v)
    av_flops = 2 * n * n * d_v
    return qkt_flops + av_flops


seq_lengths = [32, 64, 128, 256, 512, 1024, 2048]
dk = 64
flops = {n_len: attention_flops(n_len, dk) for n_len in seq_lengths}
memory_n2 = {n_len: n_len**2 for n_len in seq_lengths}

Out[31]:

Console

  Seq length           FLOPs   Attention matrix
------------------------------------------------
          32         262,144              1,024
          64       1,048,576              4,096
         128       4,194,304             16,384
         256      16,777,216             65,536
         512      67,108,864            262,144
        1024     268,435,456          1,048,576
        2048   1,073,741,824          4,194,304

The quadratic growth is visible in the numbers. Going from sequence length 512 to 2048 (4x increase) multiplies the FLOPs by 16x. Going from 64 to 2048 (32x increase) multiplies FLOPs by 1024x. This quadratic bottleneck is why large-context language models require specialized attention mechanisms. Research into efficient alternatives has produced sparse attention (attending to a fixed local window plus selected global tokens), Longformer's sliding window attention, Linformer's low-rank key-value compression, and FlashAttention's memory-efficient tiling approach. We'll explore efficient alternatives in the Attention Complexity chapter.

Out[32]:

Visualization

Line plot showing quadratic FLOPs growth with sequence length from 32 to 2048. — FLOPs for scaled dot-product attention as a function of sequence length, showing clear quadratic growth. Doubling the sequence length quadruples the computation: at length 2048, the cost is 64x that of length 256. This scaling behavior is the central motivation for efficient attention research targeting long-document and long-context applications.

Line plot showing quadratic memory growth with sequence length from 32 to 2048. — Attention matrix memory cost (number of elements) as a function of sequence length, also growing quadratically. At 2048 tokens, a single attention matrix has over 4 million entries. With 12 attention heads, 32-bit floats, and a batch size of 32, attention matrices alone require over 6 GB per layer, making long-context inference memory-bound before any other model parameters are considered.