BigBird

§ 1 · Premise

Sparse attention without theoretical guarantees

Full self-attention costs $\Theta(N^2 \cdot d_h)$ compute and stores an $N \times N$ logit matrix per head per layer. At $N = 4096$ with $d_h = 64$ and 12 heads per layer, that is ~200M float multiplies per head per layer for the logit step alone and a 256 MB activation per layer before the softmax — both quadratic in the sequence length. By mid-2020 several sparse-attention designs had reduced this cost to subquadratic, but each had a different asymptotic guarantee and none had a formal expressivity result. The two relevant predecessors:

• Sparse Transformer (Child et al. 2019) used strided + fixed patterns achieving $O(N \sqrt{N})$ attention with full reachability in two hops. Empirically successful on character-level language modeling; no theory about whether the sparse approximation preserves any of full attention’s properties.
• Longformer (Beltagy et al. 2020, arXiv 2004.05150) combined a local sliding window with task-specific “global” tokens, achieving $O(N \cdot W)$ attention. Empirically successful on long-document classification; no theory.

The open question both left: are these sparse patterns fundamentally limited compared to full attention? Are there sequence-to-sequence functions that full attention can represent but sparse-attention models provably cannot?

BigBird (Zaheer et al. 2020, arXiv 2007.14062) is the first sparse attention with a positive answer. Its construction combines three patterns — local window + global tokens + random — and the paper proves that with these three patterns the layer is (a) a universal approximator of sequence-to-sequence functions in the same sense as full attention (Yun et al. 2019, arXiv 1912.10077), and (b) Turing complete given unbounded depth and precision (Pérez et al. 2019, arXiv 1901.03429 prove this for full attention; BigBird extends the result). The construction is also $O(N)$ in attention compute, the lowest asymptotic in any well-defined sparse-attention design at the time of publication.

The contribution in one sentence: a sparse-attention design whose three-pattern union has both proven theoretical guarantees and $O(N)$ asymptotic cost — closing the “sparse-attention-but-is-it-as-expressive?” gap that prior designs had left open.

§ 2 · Derivation

Window + global + random as a sparse-graph attention

Standard self-attention defines an attention graph $G \subseteq [N] \times [N]$ where edge $(i, j) \in G$ means query $i$ attends to key $j$. Dense attention uses the complete graph $G_{\mathrm{full}} = [N]^2$. Sparse attention parameterizes a subset $G_{\mathrm{sparse}} \subseteq G_{\mathrm{full}}$:

The cost per layer is $O(|G_{\mathrm{sparse}}| \cdot d_h)$, vs $O(N^2 \cdot d_h)$ for full attention. The question is what structure $G_{\mathrm{sparse}}$ must have to preserve full- attention expressivity.

BigBird’s $G_{\mathrm{BB}}$ is the union of three sub-graphs (Zaheer et al. 2020, §2):

1. Window attention $G_W$: each query attends to $w$ consecutive keys centered (or left-windowed in the causal case) on its position. $|G_W| = N \cdot w$. The same pattern as SWA.
2. Global attention $G_G$: a designated set $\mathcal{G} \subseteq [N]$ of $g = |\mathcal{G}|$ indices, where every query attends to every $j \in \mathcal{G}$ and every $i \in \mathcal{G}$ attends to every key. $|G_G| = 2 g N - g^2$.
3. Random attention $G_R$: each query is assigned $r$ independently and uniformly sampled key indices. $|G_R| = N \cdot r$.

The total edge count is $|G_{\mathrm{BB}}| = N(w + r) + 2 g N - g^2 = O(N)$ when $w, g, r$ are constants in $N$. The Zaheer et al. defaults are $w = 256$, $g = 32$, $r = 32$, giving $\sim 300$ key slots per query at any $N$ — a 13× reduction at $N = 4096$ and an 85× reduction at $N = 16384$.

Why all three patterns? The proof of universal approximation needs the attention graph to satisfy three properties simultaneously (Zaheer et al. 2020, Theorem 1 and Appendix A):

(i) $G_{\mathrm{sparse}}$ must be connected — there must be a path between every pair of nodes. The window alone gives $O(N / w)$-diameter connectivity (a chain); not enough for any $O(\log N)$-depth construction.

(ii) The graph must have small effective diameter — bounded by a small constant independent of $N$, so that information from any token reaches any other within a fixed number of hops. Window alone fails; the strided pattern from Sparse Transformer achieves $O(\log N)$ diameter; BigBird needs $O(1)$.

(iii) The graph must admit a finite-cover argument matching Yun et al.’s universal- approximation proof for full attention — every pair of close-enough function arguments must be discriminable by some attention path.

The three patterns each contribute one property:

• Window gives local positional smoothness — needed for Property (iii)‘s discrimination on locally-clustered inputs.
• Global tokens give deterministic two-hop connectivity — any pair of non-global tokens $(i, k)$ are connected through any global token $j \in \mathcal{G}$: $i \to j$ via $G_G$‘s “every query attends to global,” then $j \to k$ via $G_G$‘s “global queries attend to every key.” Property (ii) drops to diameter 2.
• Random edges give expander-graph connectivity in expectation. For $r \geq 2$, the random subgraph $G_R$ has expected spectral gap bounded below by a constant, so the random- walk mixing time is $O(\log N)$ (Zaheer et al. 2020, Lemma 1). This gives the strong- expansion property the discrimination proof needs.

The expander-graph result. A random graph on $N$ vertices where each vertex has $r$ uniformly random out-edges is, with probability $1 - o(1)$, an $\varepsilon$-expander for $\varepsilon = \Omega(1)$ when $r \geq 3$ (Friedman 2003 on the Alon conjecture; Zaheer et al. 2020 invoke this as background). Concretely: the random pattern has spectral gap close to the Ramanujan bound, giving $O(\log N)$ random-walk mixing — meaning information from any token reaches any other in $O(\log N)$ hops through random edges alone.

Why not just use the strided pattern from Sparse Transformer? Strided patterns with stride $\ell$ achieve $O(\log_\ell N)$ diameter via stacked layers — apparently fine. The issue is the finite-cover discrimination needed in property (iii): strided patterns are periodic, so two tokens at the same residue class mod $\ell$ are connected by the same path structure as every other pair in the same residue class. The random pattern breaks this symmetry — each query has a different random key set, so the discrimination is position-specific. The universal-approximation proof in Sparse Transformer’s framework would have to construct a separate argument for each residue class; BigBird sidesteps this by using a single random pattern that works for all positions.

The two theorems. With $G_{\mathrm{BB}}$ as defined above:

(Zaheer et al. 2020, §3). For any continuous permutation-equivariant $f: \mathbb{R}^{N \times d} \to \mathbb{R}^{N \times d}$ and any $\varepsilon > 0$, there exists a BigBird transformer with depth and width $\mathrm{poly}(N, 1/\varepsilon)$ that approximates $f$ within $\varepsilon$ uniformly.

(Zaheer et al. 2020, §3.1). Given unbounded depth and arbitrary precision, a BigBird stack can simulate any Turing machine. Same statement as Pérez et al. 2019’s result for full attention.

Cost per layer. Total memory is $O(N (w + g + r))$ for the sparse attention matrix. Compute is $O(N (w + g + r) \cdot d_h)$ per head. At the defaults $w = 256, g = 32, r = 32$ and $N \leq 4096$, the cost is bounded by $O(N \cdot 320 \cdot d_h)$, asymptotically linear in $N$ but with a large constant (~320). For $N \leq 1024$ the full $N^2$ attention is actually faster.

§ 3 · Reference implementation

Three masks unioned

def bigbird_attention(q, k, v, window_size, global_idx, num_random):
    # q, k, v: [B, T, d_h]      global_idx: [G] indices of global tokens
    B, T, d = q.shape
    # 1. Window mask: |i - j| <= window_size // 2
    rows = torch.arange(T).view(T, 1)
    cols = torch.arange(T).view(1, T)
    window_mask = (cols - rows).abs() <= (window_size // 2)
    # 2. Global mask: row in global_idx OR col in global_idx
    global_mask = torch.zeros(T, T, dtype=torch.bool)
    global_mask[global_idx, :] = True
    global_mask[:, global_idx] = True
    # 3. Random mask: r random columns per row
    random_mask = torch.zeros(T, T, dtype=torch.bool)
    for i in range(T):
        sampled = torch.randperm(T)[:num_random]
        random_mask[i, sampled] = True
    full_mask = window_mask | global_mask | random_mask
    scores = (q @ k.transpose(-2, -1)) / d**0.5      # [B, T, T] — still O(T^2) in this sketch
    scores = scores.masked_fill(~full_mask, float("-inf"))
    return scores.softmax(-1) @ v

This sketch computes the full $T \times T$ score matrix then masks — illustrative but asymptotically wrong. A production implementation gathers the $w + g + r$ keys per query into a $[B, T, w + g + r, d_h]$ buffer (the “block-sparse” formulation in Zaheer et al. 2020, §4) so that the attention matmul is $O(N \cdot (w + g + r) \cdot d_h)$.

§ 4 · Empirical evidence

What BigBird and follow-ups measure

Long-document QA. Zaheer et al. 2020 Table 4 reports BigBird at $N = 4096$ matching or beating RoBERTa-Large at $N = 512$ on HotpotQA (F1 75.7 vs 73.5), TriviaQA (F1 81.9 vs 74.3), and WikiHop (accuracy 75.9 vs 72.4) — while running $\sim 4 \times$ less attention compute per layer at the longer context.

Genomics. BigBird’s most cited long-tail application is the genomics task in §5: training on chromosome-length DNA sequences ($N = 8192$ tokens) for promoter-prediction and chromatin modeling. BigBird matches the dense-attention baseline at $N = 512$ while accessing 16× longer context, giving a meaningful real-domain win on a task where standard transformers could not even fit the data.

Ablation of the three components. Zaheer et al. 2020 Table 6 ablates the random component by training BigBird with $r = 0$ (window + global only — i.e., Longformer). On the QA suite the no-random variant loses 0.5–1.5 F1 points but does not break catastrophically. The interpretation: the random component’s theoretical role (expander-graph mixing) gives an asymptotic guarantee, but in the finite-depth, finite-$N$ regime of real models, the window- plus-global pattern is empirically close to sufficient. This is the result that justified production decoders skipping the random pattern.

Random pattern in causal/decoder settings. The random pattern interacts awkwardly with autoregressive masking — a token $i$ randomly attending to $j > i$ would violate causality. The Zaheer et al. construction is encoder-only; the paper does not propose a decoder version. Independent work on decoder-side sparse attention (Sparse Transformer; later SWA + global) all used deterministic patterns.

Where production went. Production long-context decoder LLMs largely adopted window + occasional global without the random component. Mistral 7B (Jiang et al. 2023, arXiv 2310.06825) uses pure SWA. Gemma 2 / Gemma 3 (Gemma Team 2024, arXiv 2503.19786, §3.2) interleave SWA layers with full-global layers at a 5:1 ratio — BigBird without the random, modulated across depth rather than within each layer. Empirically these match BigBird’s long-context quality at substantially simpler implementation. See SWA for the descendant pattern that won at scale.

Independent reproduction. The BigBird paper’s reference code has been re-implemented by the Hugging Face team (BigBirdModel in transformers), and the long-document QA numbers have been independently reproduced on HotpotQA and Natural Questions. The Turing-completeness proof has been verified by subsequent work on sparse-attention expressivity (Sanford et al. 2022, arXiv 2211.05498, §4 cites BigBird’s argument directly).

Open questions / what isn’t measured. I don’t know of a public study isolating the contribution of random pattern at fixed total edge count. Zaheer et al.’s ablation drops $r$ to zero, but at fixed $|G_{\mathrm{BB}}|$ one could trade window size for random count and ask which choice helps more. No such sweep has been published. The theoretical argument says random is essential; the empirical evidence says window + global is sufficient — and the gap between these statements has not been closed in print.

@article{arxiv2007_14062,
  title  = {Big Bird: Transformers for Longer Sequences},
  author = {Manzil Zaheer and others (Google Research)},
  year   = {2020},
  eprint = {2007.14062},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/2007.14062}
}

@article{arxiv_2007_14062,
  title         = {Big Bird: Transformers for Longer Sequences},
  author        = {Manzil Zaheer et al. (Google Research)},
  year          = {2020},
  eprint        = {2007.14062},
  archivePrefix = {arXiv},
  url           = {https://arxiv.org/abs/2007.14062}
}

{
  "id": "arxiv_2007_14062",
  "type": "article-journal",
  "title": "Big Bird: Transformers for Longer Sequences",
  "author": [
    {
      "literal": "Manzil Zaheer et al. (Google Research)"
    }
  ],
  "issued": {
    "date-parts": [
      [
        2020
      ]
    ]
  },
  "URL": "https://arxiv.org/abs/2007.14062",
  "number": "2007.14062",
  "source": "arXiv"
}

TY  - JOUR
TI  - Big Bird: Transformers for Longer Sequences
AU  - Manzil Zaheer et al. (Google Research)
PY  - 2020
JO  - arXiv
AN  - arXiv:2007.14062
UR  - https://arxiv.org/abs/2007.14062
ER  -