Big Bird: Transformers for Longer Sequences
- Publication
- NeurIPS 2020Conference
- First submitted to arXiv
- arXiv:2007.14062
Cite this paper · BibTeX
The citation identifies the linked source version. It cites the original paper and its authors.
@misc{transformersbigbird2020,
title = {{Big Bird: Transformers for Longer Sequences}},
author = {Manzil Zaheer and Guru Guruganesh and Avinava Dubey and Joshua Ainslie and Chris Alberti and Santiago Ontanon and Philip Pham and Anirudh Ravula and Qifan Wang and Li Yang and Amr Ahmed},
year = {2020},
eprint = {2007.14062},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2007.14062}
}
The computational complexity of the Transformer's self-attention mechanism is .
When an algorithm has this kind of complexity, you might expect plenty of room for optimization.
Hmm? This introduction again?
Defining the Problem
Transformer models, such as BERT, have shown outstanding performance in various NLP tasks, primarily due to the parallel computing capability of the self-attention mechanism and modern hardware support. However, the computational and memory requirements brought by this mechanism are quadratic concerning the sequence length, limiting its direct application in tasks requiring longer contexts.
Shortly after the Longformer was proposed, the Google Brain team introduced BigBird, a Transformer variant designed specifically to handle long sequences.
Lack of Fundamental Theory
Theoretical work on full attention, and contemporary work on sparse approximation, already existed. The question here is which sparse structures preserve universal approximation and Turing completeness while using fewer connections.
Motivated by the above, the authors propose the BigBird model, which achieves excellent performance on long-sequence tasks through a sparse attention mechanism while maintaining theoretical expressive power.
Solving the Problem
Model Architecture
The concept of this paper is quite simple. You can almost understand it by looking at this picture.
In the BigBird architecture, the authors designed three components that ultimately form a sparse structure:
- Diagram (a) is the random attention mechanism that establishes connections between tokens randomly within each layer of the model.
- Diagram (b) is the Sliding Window Attention, where each token only attends to tokens within a fixed range before and after it.
- Diagram (c) is the Global Attention, where specific tokens attend to all other tokens, and other tokens attend to these specific tokens.
- Diagram (d) combines the above three mechanisms to form the BigBird attention mechanism.
Architecture Design
With random degree , window width and global-token count fixed as grows, each layer has connections.
The authors designed two different methods for selecting global tokens, compared in subsequent experiments:
-
BIGBIRD-ITC (Internal Transformer Construction)
- Global Token Selection: In this design, certain existing tokens are designated as "global" tokens, meaning they will attend to all other tokens in the sequence.
- Matrix Representation: For the selected global token index set , the corresponding adjacency matrix is adjusted so that all elements of rows and columns for each global token in are set to 1 (i.e., and ), indicating these tokens can interact with all other tokens in the sequence.
-
BIGBIRD-ETC (Extended Transformer Construction)
- Additional Global Tokens: Unlike ITC, the ETC design introduces additional global tokens (e.g., CLS tokens) specifically designed to attend to all existing tokens.
- Matrix Expansion: Add both rows and columns, producing of shape . The new global rows and columns are all ones, while the original connections remain in the other block.
Proof Beforehand
The following section is the most challenging part of the paper, where the authors prove the theoretical properties of BigBird and explain why the "random attention mechanism" is adopted.
Although we can directly use the conclusions, since we're here, let's take a brief look.
Before proving, the authors describe the theoretical framework of the self-attention mechanism:
-
Generalized Attention Mechanism
- The BigBird model uses a generalized attention mechanism that processes the sequence within each layer of the Transformer.
- The attention mechanism is described through a directed graph , where the node set is , and directed edges represent the set of dot products considered.
-
Attention Output Vector
- For each node in the graph, the generated output vector is calculated from node and its outer neighbors .
- Specifically, .
- and map to ; the value function maps to .
- is a scoring function, such as softmax or hardmax.
- is the number of heads.
-
Fully Connected Graph and Sparsification:
- If is a fully connected directed graph, it reverts to the quadratic attention mechanism described by Vaswani et al.
- The sparsification of graph is achieved by selecting a certain number of random edges between nodes, reducing computational complexity.
-
Sparse Random Graphs:
- Random graphs are used to approximate full graphs, with spectral properties similar to full graphs, acting as expanders.
- Erdős–Rényi graphs motivate the design. BigBird actually selects random keys per query and uses block sparsity for efficient hardware execution, rather than keeping every possible edge with a length-independent probability.
-
Locality and Sliding Window:
- In most NLP and computational biology contexts, much of the reference information exhibits locality, extracting information from neighboring tokens.
- The BigBird model uses a sliding window attention mechanism to address this locality.
-
Use of Global Tokens:
- Global tokens are introduced to simulate cases involving all tokens in the sequence, playing a key role in attention computation, participating in processing the entire sequence.
The above section doesn't introduce new concepts but describes how the original attention mechanism is a "special case" of the generalized attention mechanism.
This "special case" is the fully connected directed graph, so adjusting the attention graph to a "tailored" directed graph means stepping into the domain of sparse attention mechanisms.
Additionally, it explains why the authors consider random attention:
- Random links can shorten paths between distant tokens, allowing information to travel across a long sequence.
The Erdős–Rényi graph motivates that intuition; BigBird actually has each query attend to random keys alongside local windows and global tokens. The global connections are also central to the universal-approximation proof. None of this establishes that a fixed sparse graph reproduces every full-attention layer numerically for every input.
Start Proof
The encoder stack of a Transformer is essentially a series of repeated single-layer encoders, each with its own set of parameters.
This structure allows input data to be processed through multiple stages, with each layer further transforming the data based on the previous layer's output.
-
Parameterization:
- H: The number of attention heads in each encoder layer.
- m: The size of each attention head.
- q: The size of the hidden layer in the output network.
-
Attention Mechanism:
- Defined by a directed graph . Unlike traditional attention mechanisms (e.g., Vaswani et al.), this configuration adds a special token at the start of each sequence, denoted as . This token can be used for various purposes, such as representing aggregated information of the sequence or handling specific context requirements. The vertex set of graph includes this special token, i.e., .
-
Input and Output Processing:
- Despite adding an extra node at the beginning, the Transformer is conceptualized as mapping sequences from to .
- In the final output layer, it is assumed that the extra node and its vector are discarded, ensuring the output dimensions match the input.
- Positional information aligns with the token axis. Using consistently here gives a matching position matrix , avoiding the paper’s mixed transpose convention.
-
Universal Approximation:
-
The function class is defined as the set of continuous functions , with continuity defined by a specific -norm topology.
-
The distance metric used to measure the quality of function approximation is the -norm distance .
-
-
Definition: Star Graph Centered at 0
- Here, the star graph is a specific graph structure where one central node (node 0) is directly connected to all other nodes (nodes 1 to n) in the graph.
- This structure is crucial as it allows the central node to directly influence all other nodes, which is an important feature used in the subsequent proof.
-
Theorem: Universal Approximation Capacity of Sparse Attention Mechanisms
- Within the defined model class, a graph containing star (ordinary nodes attend to themselves and the global node, which attends to all ordinary nodes) admits, for every , and target continuous function, some sparse Transformer with .
- This means that such a Transformer model can approximate any continuous function in the function class .
-
Proof Step 1: Approximating with Piecewise Constant Functions
First, the function we need to handle is a continuous function defined on the bounded region . To approximate such a function, we choose to use piecewise constant functions. Specifically, we partition the [0, 1) interval into small grids (with granularity ), thus turning the entire region into a discrete point set . Within each small grid, we assume the function value is constant. This way, we can approximate the original function with a new piecewise constant function .
-
Proof Step 2: Approximating Piecewise Constant Functions with Modified Transformers
This is the most critical step of the proof. Here, we use the self-attention mechanism to produce a context mapping of the input. Each matrix and its column are mapped into a unique code, which is then used to generate a unique output column. Since we only use a sparse attention mechanism, the challenge lies in ensuring that each query can obtain sufficient information to complete this mapping. The solution is to develop a sparse shift operator that adjusts according to the range of data in the input matrix, ensuring that each column of data forms a complete and unique mapping.
-
Proof Step 3: Approximating Modified Transformers with Original Transformers
The final step is to approximate the modified Transformer model with the original Transformer model (using ReLU and softmax functions). This completes an existence argument, not a fixed-depth efficiency or training-convergence guarantee.
Turing Completeness
In fact, research by Pérez et al. shows that Transformer models based on the complete attention mechanism are Turing complete, meaning they can simulate the computation process of any Turing machine.
However, this result is based on a theoretical assumption that the model can "process data with arbitrary precision."
In practical applications, this assumption often does not hold, as Transformers are finite-state machines and cannot achieve true Turing completeness.
-
Is Sparse Attention Also Sufficient to Simulate Any Turing Machine?
The paper mentions that with appropriate adjustments, Transformers using sparse encoders and decoders can also achieve Turing completeness.
The Turing-machine simulation constructs a decoder with causal sparse connections. It is a specific encoder–decoder proof construction, not a claim that the bidirectional BigBird encoders in the experiments must decode token by token.
Moreover, in the method by Pérez et al., each token also serves as a representation of the tape history, with full attention used to move and retrieve the correct symbol on the tape.
For the implementation of the sparse attention mechanism, besides modifying the addressing scheme pointing to the history, most of the architecture can be directly applied.
This shows that even under sparse configurations, Transformers have the potential to simulate any computation process, providing a theoretical foundation for understanding and extending Transformer applications in various complex computational tasks.
Limitations of Sparse Attention
This task requires finding, for each given unit vector among unit vectors , a corresponding farthest vector . Here, "farthest" refers to the Euclidean distance in the vector space, often translating to minimizing the inner product.
In a complete attention mechanism, this task is relatively easy to solve because it allows calculating inner products for all vector pairs simultaneously. In other words, the complete self-attention mechanism can evaluate relationships among all vector pairs simultaneously, thus finding the farthest vector for each in layers.
Under OVC, for the paper’s model class with the number of heads, head size and output-network width each bounded by , a graph with only edges per layer requires layers for this task. Tildes hide polylogarithmic factors. Full attention’s constant depth still entails quadratically many pairwise operations. This is a conditional lower bound for the specified model class, not arbitrary-width models with arbitrary external computation.
This indicates that while sparse attention mechanisms can reduce computational resource consumption, solving certain types of problems may require significantly more layers, potentially becoming a limitation in practical applications.
Discussion
This section looks at the benefits of handling longer input sequences in NLP tasks. We first examine question answering (QA), then long-document summarization. These experiments help us see whether longer context improves performance on the tasks discussed below.
QA-dev
- Datasets: Including HotpotQA, Natural Questions, TriviaQA, and WikiHop.
- Metrics: Using base-sized models, reporting accuracy for WikiHop and F1 scores for HotpotQA, Natural Questions, and TriviaQA.
BigBird performs strongly, but ETC does not win every column. Table 2 gives ITC/ETC scores of 75.7/75.5 for HotpotQA Answer, 79.5/78.7 for TriviaQA, and a tie at 75.9 for WikiHop. ETC leads on several other metrics.
QA Test finetune
- Tasks and Datasets: Including HotpotQA, Natural Questions, TriviaQA, and WikiHop.
- Comparison Benchmark: Comparing the BIGBIRD-ETC model with the top three entries on the leaderboard excluding BIGBIRD.
In this experiment, BIGBIRD-ETC set new best results in several columns, notably Natural Questions long answer, TriviaQA and WikiHop. It did not lead on Natural Questions short answer or HotpotQA answer and joint F1. BIGBIRD is a single model; the authors note that several leading Natural Questions entries use ensembles, which may help explain its lower short-answer score there.
Long Document Summarization Ability
The authors test abstractive summaries of long documents in arXiv, PubMed and BigPatent. Their encoder uses BIGBIRD sparse attention, while decoder self-attention remains full. The base model starts from RoBERTa-derived weights; the large model starts from PEGASUS. In Table 4, large BIGBIRD-PEGASUS exceeds the listed PEGASUS comparison rows on ROUGE-1/2/L for all three datasets, although these comparisons do not isolate sparse attention as the sole cause. ROUGE measures overlap with reference summaries, not factual accuracy itself.
The authors suggest that a longer input lets the model gather information spread throughout a document. The table supports the usefulness of this setup on these datasets, but does not by itself measure how much of the gain comes from input length rather than the other model and training differences. That is the practical promise of BIGBIRD for tasks that need to read further into a document.
Conclusion
Compared to past models like Sparse Transformer and Longformer, we believe the main contribution of this paper is providing a detailed mathematical theory proof for sparse attention mechanisms.
To approximate the reach of full attention in a practical sparse design, the authors combine random links, sliding windows and a few global tokens. The universal-approximation theorem gives the defined global star structure as a sufficient condition.
The theory establishes existence and expressive capacity; experiments demonstrate practical benefits on the evaluated tasks. Neither guarantees that a fixed-depth model is easy to train or superior on every long-sequence problem.
Regarding the detailed proof methods, the appendix of the paper contains about 20 pages of material, which can be overwhelming. Interested readers are welcome to review the original paper for more information.