# BigBird

> BigBird makes each query block attend to a few neighbouring blocks, a few random blocks and a few global blocks, so cost is linear in sequence length. Zaheer et al. (2020) proved this sparse pattern keeps full attention's universal approximation and Turing completeness, and ran it at 4,096 tokens.

Source: https://www.mlfoundry.in/learn/bigbird  
Section: Deep Learning › Attention and Transformer Architectures  
Level: advanced · 15 min read · updated 2026-10-12

**BigBird:** is a sparse-attention Transformer in which each query attends to three sets of keys: $w$ neighbouring tokens (**window**), $r$ randomly chosen tokens (**random**), and $g$ **global** tokens that attend to and are attended by everything. The number of scores per query is $w+r+g$, independent of the length $n$, so a layer costs $O(n)$. It was introduced by Zaheer, Guruganesh, Dubey, Ainslie, Alberti, Ontañón, Pham, Ravula, Wang, Yang and Ahmed, "Big Bird: Transformers for Longer Sequences" (NeurIPS 2020).

By 2020 several sparse patterns existed: fixed strided patterns (**Sparse attention**, Child et al. 2019), sliding windows with global tokens (**Longformer**), and the global–local ETC model of Ainslie et al. (EMNLP 2020). They worked in practice, but it was not known whether sparse attention gives up any of full attention's expressive power. The Google Research team behind BigBird answered with theory and engineering together. They viewed attention as a graph and borrowed two facts from graph theory. Random graphs are **expanders**: with few edges per node, any node reaches any other in a logarithmic number of hops. **Small-world** graphs add local clustering, which matches the locality of language. They then proved that window + random + global keeps the universal-approximation and Turing-completeness properties of the full Transformer. Laid out in blocks for GPUs, the same pattern handled sequences 8 times longer than BERT's 512 on similar hardware.

## Attention as a graph

$$
\mathrm{Attn}_D(X)_i=x_i+\sum_{h=1}^{H}\sigma\!\Big(Q_h(x_i)\,K_h\big(X_{N(i)}\big)^{\!\top}\Big)\,V_h\big(X_{N(i)}\big),\qquad N(i)=\underbrace{\{\,j:|i-j|\le \tfrac{w-1}{2}\}}_{\text{window}}\ \cup\ \underbrace{R(i)}_{r\ \text{random}}\ \cup\ \underbrace{G}_{g\ \text{global}}
$$

- $D$: a directed graph on the $n$ positions; edge $i\to j$ means query $i$ scores key $j$. Full attention is the complete graph
- $N(i)$: out-neighbours of $i$; the softmax $\sigma$ runs over these keys only
- $R(i)$: $r$ keys sampled at random for query $i$ (fixed after sampling)
- $G$: global tokens: $i\in G$ attends to all $j$, and every $j$ attends to $i$
- $Q_h,K_h,V_h$: the usual per-head projections of **Multi-head attention**

Each ingredient has a job. The **window** captures local dependencies, the most frequent kind in text. The **random** edges make the graph an expander, so information crosses the sequence in $O(\log n)$ layers rather than $O(n/w)$. The **global** tokens form a star: any token reaches any other in two hops through a hub. The paper's ablations found random plus window alone fell short of BERT on its tasks, and the global tokens closed the gap.

## What the theory says

**Universal approximation.** Yun et al. (2020) proved that full Transformers can approximate any continuous sequence-to-sequence function on a compact domain. BigBird extends this: any sparse attention graph that contains a **star** (one global token connected to all positions) is also a universal approximator, using only $O(n)$ inner products per layer. **Turing completeness.** Pérez et al. (2019) showed the full encoder–decoder Transformer is Turing complete. BigBird shows that the sparse encoder–decoder, with a global token, is too. **A limit.** Sparsity is not free: the paper gives a task, finding for each vector the furthest one in the set, that one full-attention layer solves but that needs $\tilde\Omega(n)$ layers with any sparse attention of $\tilde O(n)$ edges, under a standard hardness conjecture (the Orthogonal Vectors Conjecture). The expressive power survives, but some functions may need many more layers.

## Blocks: making it fast

Gathering $r$ scattered keys per token is slow on accelerators. BigBird therefore sparsifies at the level of **blocks** of $b$ tokens: the sequence is split into $n/b$ blocks, and a query block attends to whole key blocks. Each block pair is a dense $b\times b$ product, and the gathers turn into a few large matrix multiplications. In **BigBird-ITC** (internal transformer construction) some existing blocks are made global: the first and the last in the reference code. In **BigBird-ETC** (extended transformer construction) $g$ extra global tokens are added in front, as in ETC, and can carry structured inputs such as the question or sentence markers.

**BigBird-ITC base configuration (paper and Hugging Face defaults)**

- **Block size:** $b=64$ tokens
- **Keys per query block:** 3 window blocks (192 tokens) + 3 random blocks (192) + 2 global blocks (128) = 512 keys
- **Sequence length:** 4,096 tokens = 64 blocks; the full attention matrix would have $4096^2=16.8$M entries per head
- **Pretraining:** MLM, warm-started from the public RoBERTa checkpoint, on Books, CC-News, Stories and Wikipedia
- **Tasks:** long-document QA (Natural Questions, HotpotQA, TriviaQA, WikiHop), classification, summarisation of arXiv, PubMed and BigPatent with an encoder–decoder (sparse encoder, full decoder), and DNA sequences (promoter-region and chromatin-profile prediction)
- **Hugging Face:** `attention_type="block_sparse"`, `block_size=64`, `num_random_blocks=3`, `max_position_embeddings=4096`

> Figure: Block-level attention for 16 blocks of 64 tokens (1,024 tokens). Rows are query blocks, columns key blocks. With the base configuration (3 window, 3 random, 2 global blocks, ITC) an ordinary query block reads 8 blocks, 512 keys, and the layer scores 142 of 256 block pairs. Every block has read every other block after 2 layers. Remove random and global blocks and only the band is left: 46 pairs, but block 0 needs 15 layers to reach block 15. Add 3 random blocks back (no global): 94 pairs and 3 layers, the expander effect. The strip under the map shows, for the selected query block, after how many layers it has read each block. The right panel builds the same pattern at 4,096 tokens: 2,547,712 scores per head per layer, 15.19% of 16,777,216, about 622 keys per query on average. Switch to ETC to prepend 2 extra global blocks (2,629,632 of 17,842,176 scores at 4,096 + 128 tokens), and resample the random blocks to see that the counts do not change.

## Worked example: the block pattern at 4,096 tokens

Ablating the three components (ITC, b = 64, n = 4096, window of 3 blocks; scores per head per layer computed in Node; layers = maximum over query blocks of the hops needed to read every block, the graph diameter)

| components | scores | fraction of n² | layers until all read all |
| --- | --- | --- | --- |
| window (3 blocks) | 778,240 | 4.64% | 63 |
| window + 2 global | 1,785,856 | 10.64% | 2 |
| window + 3 random | 1,564,672 | 9.33% | 5 or 6 (depends on the draw) |
| window + 3 random + 2 global (BigBird) | 2,547,712 | 15.19% | 2 |
| full attention | 16,777,216 | 100% | 1 |

**Counting the BigBird row**

1. 64 blocks. The 2 global blocks (0 and 63) read all 64 key blocks: $2\cdot64=128$ block pairs.
2. Blocks 1 and 62: their window $\{0,1,2\}$ (or $\{61,62,63\}$) already contains a global block, so they read $3+1+3=7$ blocks: $2\cdot7=14$ pairs.
3. Blocks 2 to 61 read 3 window + 2 global + 3 random $=8$ blocks: $60\cdot8=480$ pairs.
4. Total $128+14+480=622$ block pairs, each a $64\times64$ tile: $622\cdot4096=2{,}547{,}712$ scores, $622/64^2=15.19\%$ of full attention.
5. Ordinary queries read 512 keys whatever $n$ is. At $n=8192$ the same pattern scores 5,169,152 entries, 7.70% of $8192^2$: the fraction halves when $n$ doubles.
6. Without random or global blocks, information moves one block per layer, so block 0 needs 63 layers to read block 63. Three random blocks cut this to 5 or 6, close to $\log_2 64=6$. Global blocks give 2: any block reads a global block, which has read everything.

```python
import torch

def bigbird_block_mask(nb, w=3, r=3, g=2, seed=0):
    gen = torch.Generator().manual_seed(seed)
    i, j = torch.arange(nb)[:, None], torch.arange(nb)[None, :]
    m = (i - j).abs() <= w // 2                       # window blocks
    glob = torch.zeros(nb, dtype=torch.bool)
    glob[: (g + 1) // 2] = True                       # ITC: first block(s) ...
    if g >= 2:
        glob[nb - g // 2:] = True                     # ... and last block(s) are global
    m |= glob[:, None] | glob[None, :]
    for q in range(nb):
        if glob[q]:
            continue
        free = (~m[q]).nonzero().flatten()            # not window, not global
        m[q, free[torch.randperm(len(free), generator=gen)[:r]]] = True   # r random blocks
    return m

m = bigbird_block_mask(64)                            # 4096 tokens in blocks of 64
print(m.sum(1)[:4].tolist(), m.sum(1)[10].item())     # [64, 7, 8, 8] 8
print(m.sum().item())                                 # 622 block pairs
tok = m.repeat_interleave(64, 0).repeat_interleave(64, 1)
print(tok.shape, tok.float().mean().item())           # torch.Size([4096, 4096]) 0.15185546875

from transformers import BigBirdModel
model = BigBirdModel.from_pretrained("google/bigbird-roberta-base", attention_type="block_sparse",
                                     block_size=64, num_random_blocks=3)
x = torch.randint(5, 1000, (1, 4096))
print(model(x).last_hidden_state.shape)               # torch.Size([1, 4096, 768])
```

BigBird-ITC block mask, its token-level density, and the Hugging Face model

> **Short inputs silently fall back to full attention:** The block-sparse kernel needs enough blocks for the window, global and random sets not to overlap. The Hugging Face implementation switches to full attention, with only a warning, when the sequence has at most $(5+2r)\,b$ tokens: 704 with the defaults $r=3$, $b=64$. Benchmarks on 512-token inputs therefore measure plain BERT-style attention. Sequence lengths must also be a multiple of $b$; the model pads them.

> **Why random edges, not just a wider window:** A window of $w$ blocks moves information $\lfloor w/2\rfloor$ blocks per layer, so crossing $n/b$ blocks takes $O(n/(wb))$ layers. Spending the same budget on random blocks gives an expander, in which almost every pair of blocks is connected in $O(\log n)$ hops. In the table, 3 random blocks reduce 63 layers to 5 or 6, while widening the window from 3 to 7 blocks (3 per side) would still need $63/3=21$. Global tokens are stronger still (2 hops), but every global token adds a full row and column, an $O(n)$ cost.

> **Random means a fixed sparsity pattern:** The random blocks are part of the attention graph, not a regulariser like dropout: the theory and the expander argument are about a given sparse graph. Implementations differ in when they draw it (with a fixed seed, or anew on each call), so check before relying on bit-identical outputs. In the summarisation models BigBird is used only in the encoder; the decoder keeps full **Causal attention** over the short summary.

**Strengths**

- $O(n)$ attention: a constant $w+r+g$ keys per query (512 tokens in the base setting)
- Theory: universal approximation and Turing completeness are kept with a global token
- Block layout turns sparse gathers into dense tiles that run well on GPUs and TPUs
- Warm-starts from RoBERTa; strong long-document QA, summarisation and genomics results

**Limitations**

- Some functions need $\tilde\Omega(n)$ sparse layers that full attention computes in one
- Block granularity: all 64 tokens of a block share the same key set
- Below about $(5+2r)b$ tokens there is no saving; implementations fall back to full attention
- Random gathers and global rows complicate kernels; fused dense kernels such as FlashAttention often win at moderate lengths

**Question:** In BigBird-ITC with b = 64, 3 window, 3 random and 2 global blocks, how many keys does an ordinary query token read at n = 4,096, and at n = 16,384?

- A. 512 and 512
- B. 512 and 2,048
- C. 4,096 and 16,384
- D. 192 and 192

**Answer:** A. 512 and 512 — $(3+3+2)\cdot64=512$ keys, independent of $n$. That constant is what makes the layer $O(n)$. Only the 2 global blocks' rows grow with $n$, adding $2\cdot64\cdot n$ scores.

**Question:** Which component do BigBird's universal-approximation and Turing-completeness proofs rely on?

- A. The random blocks
- B. Global tokens (a star graph), so every token is two hops from every other
- C. A block size of exactly 64
- D. Relative position embeddings

**Answer:** B. Global tokens (a star graph), so every token is two hops from every other — The constructions use a global token connected to all positions, which can collect and broadcast information. Random edges explain the empirical efficiency (short paths with few edges), but the theorems are stated for sparse graphs that contain the star.

**Key points**

- BigBird keys per query: window $w$ + random $r$ + global $g$, independent of $n$; base ITC with $b=64$: $(3+3+2)\cdot64=512$ keys at 4,096 tokens.
- Zaheer et al. (NeurIPS 2020): sparse attention with a global token is a universal approximator of sequence-to-sequence functions and Turing complete, with $O(n)$ inner products per layer.
- Random blocks make the attention graph an expander (about $\log n$ layers to connect all blocks); global blocks connect everything in 2 hops.
- ITC turns existing blocks global; ETC adds extra global tokens that can hold structured input.
- At 4,096 tokens the base pattern computes 15.19% of the full attention scores; the fraction halves with each doubling of $n$.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
