Definition
BigBird is a sparse-attention Transformer in which each query attends to three sets of keys: neighbouring tokens (window), randomly chosen tokens (random), and global tokens that attend to and are attended by everything. The number of scores per query is , independent of the length , so a layer costs . 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
- a directed graph on the positions; edge means query scores key . Full attention is the complete graph
- out-neighbours of ; the softmax runs over these keys only
- keys sampled at random for query (fixed after sampling)
- global tokens: attends to all , and every attends to
- 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 layers rather than . 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 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 layers with any sparse attention of 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 scattered keys per token is slow on accelerators. BigBird therefore sparsifies at the level of blocks of tokens: the sequence is split into blocks, and a query block attends to whole key blocks. Each block pair is a dense 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) 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
- 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 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
Worked example: the block pattern at 4,096 tokens
| 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
- 164 blocks. The 2 global blocks (0 and 63) read all 64 key blocks: block pairs.
- 2Blocks 1 and 62: their window (or ) already contains a global block, so they read blocks: pairs.
- 3Blocks 2 to 61 read 3 window + 2 global + 3 random blocks: pairs.
- 4Total block pairs, each a tile: scores, of full attention.
- 5Ordinary queries read 512 keys whatever is. At the same pattern scores 5,169,152 entries, 7.70% of : the fraction halves when doubles.
- 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 . Global blocks give 2: any block reads a global block, which has read everything.
1import torch23def 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 blocks7 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 global11 m |= glob[:, None] | glob[None, :]12 for q in range(nb):13 if glob[q]:14 continue15 free = (~m[q]).nonzero().flatten() # not window, not global16 m[q, free[torch.randperm(len(free), generator=gen)[:r]]] = True # r random blocks17 return m1819m = bigbird_block_mask(64) # 4096 tokens in blocks of 6420print(m.sum(1)[:4].tolist(), m.sum(1)[10].item()) # [64, 7, 8, 8] 821print(m.sum().item()) # 622 block pairs22tok = m.repeat_interleave(64, 0).repeat_interleave(64, 1)23print(tok.shape, tok.float().mean().item()) # torch.Size([4096, 4096]) 0.151855468752425from transformers import BigBirdModel26model = 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])Use when
- + attention: a constant 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 sparse layers that full attention computes in one
- −Block granularity: all 64 tokens of a block share the same key set
- −Below about 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 + random + global , independent of ; base ITC with : 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 inner products per layer.
- ✓Random blocks make the attention graph an expander (about 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 .