Linear Attention › Computational Complexity Analysis

Michael BrenndoerferUpdated June 28, 20253 min read
Language AI HandbookAll chapters
Part 17 of 67Efficient Attention
Chapter 123Linear Attention › Computational Complexity Analysis
Reading section 6 of 15 · Computational Complexity Analysis · 3 minSection 6 of 15 · 3 min

Book contents

Language AI Handbook67 parts · 513 chaptersView the whole book →
Active chapter 123 of 513

Section 6 of 15 · 3 min read

Linear Attention › Computational Complexity AnalysisOne section · Sections in this chapter6 / 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

Let's rigorously compare the computational requirements of standard and linear attention across different sequence lengths.

In[14]:
Code
def flops_standard_attention(n, d):
    """
    FLOPs for standard attention.
    - Q @ K^T: 2 * n * n * d
    - Softmax: ~5 * n * n
    - Weights @ V: 2 * n * n * d
    """
    qk_flops = 2 * n * n * d
    softmax_flops = 5 * n * n
    wv_flops = 2 * n * n * d
    return qk_flops + softmax_flops + wv_flops


def flops_linear_attention(n, d, D=None):
    """
    FLOPs for linear attention.
    - Feature map: ~2 * n * d (depends on feature map)
    - K'^T @ V: 2 * n * D * d
    - Q' @ KV: 2 * n * D * d
    - Normalization: 2 * n * D + n
    """
    if D is None:
        D = d  # Feature dimension equals model dimension

    feature_flops = 2 * n * d  # Simplified
    kv_flops = 2 * n * D * d
    qkv_flops = 2 * n * D * d
    norm_flops = 2 * n * D + n

    return feature_flops + kv_flops + qkv_flops + norm_flops


# Compare across sequence lengths
sequence_lengths = [128, 256, 512, 1024, 2048, 4096, 8192, 16384]
d = 64  # Model dimension
Out[15]:
Console
FLOPs Comparison: Standard vs Linear Attention

Model dimension d = 64

Seq Len    Standard           Linear                Speedup
------------------------------------------------------------
128        4.3M               2.1M                      2.0x
256        17.1M              4.3M                      4.0x
512        68.4M              8.5M                      8.0x
1024       273.7M             17.0M                    16.1x
2048       1.09G              34.1M                    32.1x
4096       4.38G              68.2M                    64.2x
8192       17.52G             136.3M                  128.5x
16384      70.06G             272.6M                  257.0x

The speedup grows linearly with sequence length. At 128 tokens, linear attention is only marginally faster. At 16,384 tokens, it's over 100x faster. This is the power of eliminating the quadratic term: the longer the sequence, the greater the benefit.

Out[16]:
Visualization
Log-scale line plot comparing standard O(n^2 d) attention with linear O(nd^2) attention, showing diverging curves as sequence length increases.
Computational complexity comparison showing the quadratic growth of standard attention versus the linear growth of linear attention. The crossover point where they become equal depends on the model dimension, but linear attention's advantage grows unboundedly for longer sequences.

The log-scale plot reveals the essential difference: standard attention curves have slope 2 (quadratic), while linear attention curves have slope 1 (linear). All curves for the same algorithm are parallel, shifted only by the constant factor from the model dimension.