Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

BigBird › Complexity Analysis

Michael BrenndoerferUpdated June 24, 20253 min read

Language AI HandbookAll chapters

Part 17 of 67Efficient Attention

Chapter 122BigBird › Complexity Analysis

Reading section 6 of 12 · Complexity Analysis · 3 minSection 6 of 12 · 3 min

Section 6 of 12 · 3 min read

BigBird › Complexity AnalysisOne section · Sections in this chapter6 / 12 ↓

Sections in this chapter12

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 analyze the computational and memory complexity of BigBird attention compared to standard full attention:

In[19]:

Code

def calculate_attention_complexity(
    seq_len,
    d_model,
    window_size=64,
    num_global=4,
    num_random=5,
):
    """
    Calculate approximate FLOPs and memory for attention mechanisms.

    Returns both full attention and BigBird complexity estimates.
    """
    # Full attention
    # QK^T: n * n * d multiplications
    # Softmax: n * n operations
    # Attention @ V: n * n * d multiplications
    full_flops = 2 * seq_len * seq_len * d_model
    full_memory = seq_len * seq_len  # Attention matrix

    # BigBird attention
    # Each token attends to approximately:
    # - 2 * window_size + 1 local neighbors
    # - num_global global tokens
    # - num_random random tokens
    # Plus: global tokens attend to all (num_global * seq_len)

    local_per_token = 2 * window_size + 1
    connections_per_regular_token = local_per_token + num_global + num_random
    regular_tokens = seq_len - num_global

    total_connections = (
        num_global * seq_len  # Global tokens attend to all
        + regular_tokens * connections_per_regular_token
    )

    bigbird_flops = 2 * total_connections * d_model
    bigbird_memory = total_connections

    return {
        "full_flops": full_flops,
        "full_memory": full_memory,
        "bigbird_flops": bigbird_flops,
        "bigbird_memory": bigbird_memory,
        "flops_ratio": full_flops / bigbird_flops,
        "memory_ratio": full_memory / bigbird_memory,
    }


# Analyze at different sequence lengths
sequence_lengths = [512, 1024, 2048, 4096, 8192, 16384]
d_model = 768  # BERT-base dimension

complexity_data = []
for n in sequence_lengths:
    result = calculate_attention_complexity(
        n, d_model, window_size=64, num_global=4, num_random=5
    )
    result["seq_len"] = n
    complexity_data.append(result)

Out[20]:

Console

Complexity comparison (d_model=768, window=64, global=4, random=5):
----------------------------------------------------------------------
   Seq Len    Full Attn      BigBird    Speedup    Mem Ratio
----------------------------------------------------------------------
       512      262,144       72,152        3.6x         3.6x
     1,024    1,048,576      144,856        7.2x         7.2x
     2,048    4,194,304      290,264       14.4x        14.4x
     4,096   16,777,216      581,080       28.9x        28.9x
     8,192   67,108,864    1,162,712       57.7x        57.7x
    16,384  268,435,456    2,325,976      115.4x       115.4x

Out[21]:

Visualization

Log-scale line plot comparing memory usage of full attention and BigBird attention across sequence lengths from 512 to 16384 tokens. — Memory complexity scaling of full attention versus BigBird attention. Full attention scales quadratically with sequence length (blue), while BigBird scales linearly (orange). At 16K tokens, BigBird requires approximately 100x less memory for the attention matrix.

The log-scale plot clearly shows the difference between quadratic and linear scaling. For full attention, the number of attention scores is:

\text{FullAttentionSize} = n^2

For BigBird, the approximate number is:

\text{BigBirdSize} \approx g \cdot n + (n - g) \cdot (2w + 1 + g + r)

where:

$n$ : sequence length
$g$ : number of global tokens (which each attend to all $n$ positions)
$w$ : one-sided window size
$r$ : number of random connections per non-global token

At 4,096 tokens, full attention requires 16 million attention scores. BigBird, with its sparse pattern, needs only about 600,000, a roughly 25x reduction. At 16,384 tokens, the gap widens to nearly 100x.