Back to paper library
arXiv 2020NeurIPS 2020Language & TransformersPaper notes

BigBird

BigBird Attention Mechanism

Original paper

Big Bird: Transformers for Longer Sequences

Paper authors

Manzil Zaheer · Guru Guruganesh · Avinava Dubey …

Show all 11 authors

Manzil Zaheer · Guru Guruganesh · Avinava Dubey · Joshua Ainslie · Chris Alberti · Santiago Ontanon · Philip Pham · Anirudh Ravula · Qifan Wang · Li Yang · Amr Ahmed

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}
}
On this page

The computational complexity of the Transformer's self-attention mechanism is O(n2)O(n^2).

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 rr, window width ww and global-token count gg fixed as nn grows, each layer has O(n(r+w+g))=O(n)O(n(r+w+g))=O(n) 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 GG, the corresponding adjacency matrix AA is adjusted so that all elements of rows and columns for each global token ii in AA are set to 1 (i.e., A(i,:)=1A(i, :) = 1 and A(:,i)=1A(:, i) = 1), 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 gg rows and gg columns, producing BB of shape (n+g)×(n+g)(n+g)\times(n+g). 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:

  1. Generalized Attention Mechanism

    • The BigBird model uses a generalized attention mechanism that processes the sequence X=(x1,…,xn)X = (x_1, \ldots, x_n) within each layer of the Transformer.
    • The attention mechanism is described through a directed graph DD, where the node set is [n]={1,…,n}[n] = \{1, \ldots, n\}, and directed edges represent the set of dot products considered.
  2. Attention Output Vector

    • For each node ii in the graph, the generated output vector ATTND(X)i\text{ATTND}(X)_i is calculated from node ii and its outer neighbors N(i)N(i).
    • Specifically, ATTND(X)i=xi+∑h=1Hσ(Qh(xi)Kh(XN(i))T)⋅Vh(XN(i))\text{ATTN}_{D}(X)_i = x_i + \sum_{h=1}^H \sigma \left(Q_h(x_i) K_h(X_{N(i)})^T\right) \cdot V_h(X_{N(i)}).
    • QhQ_h and KhK_h map Rd\mathbb{R}^d to Rm\mathbb{R}^m; the value function VhV_h maps Rd\mathbb{R}^d to Rd\mathbb{R}^d.
    • σ\sigma is a scoring function, such as softmax or hardmax.
    • HH is the number of heads.
  3. Fully Connected Graph and Sparsification:

    • If DD is a fully connected directed graph, it reverts to the quadratic attention mechanism described by Vaswani et al.
    • The sparsification of graph DD is achieved by selecting a certain number of random edges between nodes, reducing computational complexity.
  4. 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 rr random keys per query and uses block sparsity for efficient hardware execution, rather than keeping every possible edge with a length-independent probability.
  5. 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.
  6. 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 rr 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 DD. Unlike traditional attention mechanisms (e.g., Vaswani et al.), this configuration adds a special token at the start of each sequence, denoted as x0x_0. 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 DD includes this special token, i.e., {0}∪[n]={0,1,2,…,n}\{0\} \cup [n] = \{0, 1, 2, \ldots, n\}.
  • Input and Output Processing:

    • Despite adding an extra node x0x_0 at the beginning, the Transformer is conceptualized as mapping sequences from Rn×d\mathbb{R}^{n \times d} to Rn×d\mathbb{R}^{n \times d}.
    • 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 X∈Rn×dX\in\mathbb{R}^{n\times d} consistently here gives a matching position matrix E∈Rn×dE\in\mathbb{R}^{n\times d}, avoiding the paper’s mixed transpose convention.
  • Universal Approximation:

    • The function class FCD\text{FCD} is defined as the set of continuous functions f:[0,1]n×d→Rn×df: [0, 1]^{n \times d} \to \mathbb{R}^{n \times d}, with continuity defined by a specific pp-norm topology.

    • The distance metric used to measure the quality of function approximation is the pp-norm distance dp(f1,f2)=(∫∥f1(X)−f2(X)∥p dX)1/pd_p(f_1, f_2) = \left(\int \|f_1(X) - f_2(X)\|^p \, dX\right)^{1/p}.

  • Definition: Star Graph Centered at 0 SS

    • Here, the star graph SS 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 SS (ordinary nodes attend to themselves and the global node, which attends to all ordinary nodes) admits, for every 1<p<∞1<p<\infty, ϵ>0\epsilon>0 and target continuous function, some sparse Transformer with dp(f,g)≤ϵd_p(f,g)\leq\epsilon.
    • This means that such a Transformer model can approximate any continuous function in the function class FCDFCD.
  • Proof Step 1: Approximating FCDFCD with Piecewise Constant Functions

    First, the function ff we need to handle is a continuous function defined on the bounded region [0,1)n×d[0,1)^{n\times d}. To approximate such a function, we choose to use piecewise constant functions. Specifically, we partition the [0, 1) interval into small grids (with granularity δ\delta), thus turning the entire region into a discrete point set GδG_{\delta}. Within each small grid, we assume the function value is constant. This way, we can approximate the original function ff with a new piecewise constant function fˉ\bar{f}.

  • 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 XX and its column xix_i 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 uju_j among nn unit vectors {u1,...,un}\{u_1, ..., u_n\}, a corresponding farthest vector uj∗u_j^*. 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 O(1)O(1) layers.

Under OVC, for the paper’s model class with the number of heads, head size and output-network width each bounded by O(d)O(d), a graph with only O~(n)\tilde O(n) edges per layer requires Ω~(n1−o(1))\tilde\Omega(n^{1-o(1)}) 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.