BigBird › BigBird

Standard transformers struggle with long documents because their attention mechanism scales quadratically with sequence length. For a sequence of $n$ tokens, full self-attention computes $n^2$ attention scores, meaning a 4,096-token document requires computing and storing over 16 million scores ($4096^2 = 16,777,216$). This quickly exhausts GPU memory. BigBird addresses this bottleneck by combining three complementary attention patterns: sliding window attention for local context, global tokens for long-range communication, and random attention for efficient graph connectivity. This hybrid approach reduces complexity from $O(n^2)$ to $O(n)$ while preserving the model's ability to reason over entire documents.

BigBird is significant for both its practical efficiency and its theoretical foundation. The authors proved that their sparse attention pattern can approximate any full attention function and that the random attention component makes the pattern a universal approximator of sequence-to-sequence functions. This chapter explores the BigBird attention pattern, the mathematical justification for random connections, and how this architecture compares to Longformer and other sparse attention approaches.