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.

15 min read1016 wordsadvanced0 viewsupdated 2026-10-12

Definition

BigBird is a sparse-attention Transformer in which each query attends to three sets of keys: ww neighbouring tokens (window), rr randomly chosen tokens (random), and gg global tokens that attend to and are attended by everything. The number of scores per query is w+r+gw+r+g, independent of the length nn, so a layer costs O(n)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

AttnD(X)i=xi+∑h=1Hσ ⁣(Qh(xi) Kh(XN(i)) ⁣⊤) Vh(XN(i)),N(i)={ j:∣i−j∣≤w−12}⏟window ∪ R(i)⏟r random ∪ G⏟g global\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}}
DD
a directed graph on the nn positions; edge i→ji\to j means query ii scores key jj. Full attention is the complete graph
N(i)N(i)
out-neighbours of ii; the softmax σ\sigma runs over these keys only
R(i)R(i)
rr keys sampled at random for query ii (fixed after sampling)
GG
global tokens: i∈Gi\in G attends to all jj, and every jj attends to ii
Qh,Kh,VhQ_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)O(\log n) layers rather than O(n/w)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)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 Ω~(n)\tilde\Omega(n) layers with any sparse attention of O~(n)\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 rr scattered keys per token is slow on accelerators. BigBird therefore sparsifies at the level of blocks of bb tokens: the sequence is split into n/bn/b blocks, and a query block attends to whole key blocks. Each block pair is a dense b×bb\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) gg 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=64b=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 40962=16.84096^2=16.8M 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
rows = query blocks, columns = key blocks, each block = 64 tokens (ITC)00224466881010121214141515■ window ■ global ■ random · click a rowlayers before block 6 has read each block1112210121222221this figure: 16 blocksblock 6 reads 8 blocks (512 keys)block pairs scored 142 of 256 (55.5%)layers until all read all 2mean over query blocks 1.88full attention: 1 layer, 256 pairssame pattern at 4096 tokensb = 64: 64 input blocksscores / head / layer 2,547,712full attention 16,777,216fraction 15.19%keys per query (mean) 622ordinary query block: 3 window + 3 random + 2 global = 8 key blocks, independent of n
variant
window blocksglobal blocks
fig.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

componentsscoresfraction of n²layers until all read all
window (3 blocks)778,2404.64%63
window + 2 global1,785,85610.64%2
window + 3 random1,564,6729.33%5 or 6 (depends on the draw)
window + 3 random + 2 global (BigBird)2,547,71215.19%2
full attention16,777,216100%1
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)

Counting the BigBird row

  1. 164 blocks. The 2 global blocks (0 and 63) read all 64 key blocks: 2⋅64=1282\cdot64=128 block pairs.
  2. 2Blocks 1 and 62: their window {0,1,2}\{0,1,2\} (or {61,62,63}\{61,62,63\}) already contains a global block, so they read 3+1+3=73+1+3=7 blocks: 2⋅7=142\cdot7=14 pairs.
  3. 3Blocks 2 to 61 read 3 window + 2 global + 3 random =8=8 blocks: 60⋅8=48060\cdot8=480 pairs.
  4. 4Total 128+14+480=622128+14+480=622 block pairs, each a 64×6464\times64 tile: 622⋅4096=2,547,712622\cdot4096=2{,}547{,}712 scores, 622/642=15.19%622/64^2=15.19\% of full attention.
  5. 5Ordinary queries read 512 keys whatever nn is. At n=8192n=8192 the same pattern scores 5,169,152 entries, 7.70% of 819228192^2: the fraction halves when nn doubles.
  6. 6Without 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⁡264=6\log_2 64=6. Global blocks give 2: any block reads a global block, which has read everything.
python
1import torch
2
3def bigbird_block_mask(nb, w=3, r=3, g=2, seed=0):
4 gen = torch.Generator().manual_seed(seed)
5 i, j = torch.arange(nb)[:, None], torch.arange(nb)[None, :]
6 m = (i - j).abs() <= w // 2 # window blocks
7 glob = torch.zeros(nb, dtype=torch.bool)
8 glob[: (g + 1) // 2] = True # ITC: first block(s) ...
9 if g >= 2:
10 glob[nb - g // 2:] = True # ... and last block(s) are global
11 m |= glob[:, None] | glob[None, :]
12 for q in range(nb):
13 if glob[q]:
14 continue
15 free = (~m[q]).nonzero().flatten() # not window, not global
16 m[q, free[torch.randperm(len(free), generator=gen)[:r]]] = True # r random blocks
17 return m
18
19m = bigbird_block_mask(64) # 4096 tokens in blocks of 64
20print(m.sum(1)[:4].tolist(), m.sum(1)[10].item()) # [64, 7, 8, 8] 8
21print(m.sum().item()) # 622 block pairs
22tok = m.repeat_interleave(64, 0).repeat_interleave(64, 1)
23print(tok.shape, tok.float().mean().item()) # torch.Size([4096, 4096]) 0.15185546875
24
25from transformers import BigBirdModel
26model = BigBirdModel.from_pretrained("google/bigbird-roberta-base", attention_type="block_sparse",
27 block_size=64, num_random_blocks=3)
28x = torch.randint(5, 1000, (1, 4096))
29print(model(x).last_hidden_state.shape) # torch.Size([1, 4096, 768])
BigBird-ITC block mask, its token-level density, and the Hugging Face model

Use when

  • +O(n)O(n) attention: a constant w+r+gw+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

Avoid when

  • −Some functions need Ω~(n)\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(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

Check yourself

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?

Check yourself

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

Remember

  • ✓BigBird keys per query: window ww + random rr + global gg, independent of nn; base ITC with b=64b=64: (3+3+2)⋅64=512(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)O(n) inner products per layer.
  • ✓Random blocks make the attention graph an expander (about log⁡n\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 nn.
← back to Deep Learning roadmap