BigBird › Summary

BigBird extends the sparse attention paradigm by adding random attention connections to the local-window-plus-global-tokens pattern pioneered by Longformer. This addition is not arbitrary: random connections reduce the graph diameter from $O(n/w)$ to $O(\log n)$, where $n$ is the sequence length and $w$ is the window size. With logarithmic diameter, information can propagate through the entire sequence in just a few attention layers.

Key takeaways from this chapter:

• Three-component attention: BigBird combines sliding window attention for local context, global tokens for long-range hubs, and random attention for shortcuts between distant positions. Each component serves a distinct purpose in maintaining model expressiveness.

• Theoretical guarantees: The BigBird paper proved that their sparse pattern is Turing complete and can approximate any sequence-to-sequence function computable by full attention. These proofs depend on the random connections.

• Linear complexity: BigBird achieves $O(n)$ time and memory complexity by fixing the number of attended positions per token to a constant independent of sequence length.

• Graph diameter reduction: Random attention connections act as shortcuts in the attention graph, reducing the diameter from linear to logarithmic and enabling information to flow between any two positions in just a few layers.

• Practical trade-offs: While theoretically elegant, BigBird requires careful implementation to realize its efficiency gains. The fixed attention pattern may not be optimal for all inputs.

• Applications: BigBird enables processing of long documents (legal, scientific, financial), genomic sequences, and other domains where context windows of 4K-16K tokens are needed.

The next chapter explores linear attention mechanisms, which take a fundamentally different approach to efficiency by reformulating the attention computation to avoid materializing the attention matrix entirely.