Understanding BigBird's Block Sparse Attention
BigBird addresses the $O(n^2)$ time and memory complexity of standard Transformer models, allowing them to handle sequences up to 4096 tokens. By replacing full attention with a block sparse attention mechanism, BigBird achieves state-of-the-art results on long-sequence tasks such as long document summarization and question-answering with long contexts.
Block Sparse Attention Mechanism
BigBird's block sparse attention is an approximation of BERT's full attention designed for efficiency rather than superiority. It reduces the number of tokens a query token must attend to by combining three distinct types of attention:
- Sliding Attention: Tokens attend to their immediate neighbors. This captures local dependencies, as words in a sequence are typically highly dependent on neighboring tokens.
- Global Tokens: A small set of tokens attend to every other token in the sequence and are attended by every other token. This allows information to travel across the sequence more rapidly than sliding attention alone.
- Random Tokens: A few tokens are selected randomly to attend to other tokens, further reducing the distance information must travel between distant nodes in the sequence graph.
While full attention allows information to transfer between any two tokens in a single layer, block sparse attention may require multiple layers for information to travel across the sequence. The combination of global and random connections ensures that information can travel rapidly with only a few layers.
Technical Implementation
To implement this efficiently on GPUs and TPUs, BigBird uses a block-based approach. The sequence is divided into blocks of size $b$.
Attention Calculation by Block
- First and Last Blocks: The first block ($q_1$) and the last block ($q_n$) perform normal attention operations against all other tokens in the sequence.
- Middle Blocks: For tokens in blocks $q_{3:n-2}$, the model gathers global, sliding, and random keys and computes attention only over those selected keys.
- Boundary Blocks: Blocks $q_2$ and $q_{n-1}$ gather a specific subset of keys (including the first block, the last block, and nearby sliding blocks) to maintain the sparse structure.
Complexity Comparison
BigBird reduces the computational burden significantly as sequence length increases. Compared to BERT's quadratic scaling, BigBird scales linearly:
| Attention Type | Sequence Length | Time & Memory Complexity |
|---|---|---|
| Original Full (BERT) | 512 | $T$ |
| Original Full (BERT) | 1024 | $4 imes T$ |
| Original Full (BERT) | 4096 | $64 imes T$ |
| Block Sparse (BigBird) | 1024 | $2 imes T$ |
| Block Sparse (BigBird) | 4096 | $8 imes T$ |
Training Strategies: ITC vs. ETC
BigBird can be trained using two different strategies:
- Internal Transformer Construction (ITC): Uses a small number of global tokens. It requires less compute and is sufficient for many tasks.
- Extended Transformer Construction (ETC): Adds additional global tokens. This is particularly useful for tasks like question-answering, where the entire question may need to be attended to globally by the context tokens.
Integration with Hugging Face Transformers
BigBird is available in the transformers library via BigBirdModel. Key implementation details include:
- Sequence Length Requirements: Sequence length must be a multiple of the
block_size. Hugging Face automatically pads sequences to the smallest multiple of the block size. - Automatic Fallback: If the sequence length is too short to support the required global, random, and sliding tokens, or if the model is used as a decoder (
BigBirdForCausalLM), the library automatically switchesattention_typetooriginal_full. - Recommended Usage: The authors recommend setting
attention_type="original_full"for sequences shorter than 1024 tokens.
Available checkpoints include bigbird-roberta-base, bigbird-roberta-large, and bigbird-base-trivia-itc.