PaperlayerView exact revision on arXiv

Source-linked AI summary

Big Bird: Transformers for Longer Sequences

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

arXiv:2007.14062v2cs.LGcs.CLstat.ML

TL;DR

Full self-attention is limited by quadratic dependence on sequence length, restricting access to tasks that require longer context. BIGBIRD replaces it with linear sparse attention using global, local, and random connections, while retaining theoretical expressivity and enabling longer sequences. The paper reports benefits across NLP and genomics applications, including support for 8x longer sequences and state-of-the-art results on several NLP tasks.

  • Problem

    Full self-attention has quadratic computational and memory requirements in sequence length, limiting applications that require larger context.

  • Method

    BIGBIRD is a sparse attention mechanism combining global tokens, local neighboring-token attention, and random-token attention with linear complexity.

  • Results

    BIGBIRD preserves universal approximation and Turing completeness, supports 8x longer sequences, and achieves state-of-the-art performance on question answering and document summarization tasks.

  • Takeaways & Limitations

    BIGBIRD extends attention-based modeling to longer-context NLP tasks and enables contextual language modeling for DNA sequences and downstream genomics prediction.

  • Takeaways & Limitations

    Some problems solvable by full attention in O(1) layers require approximately linear layers for sparse-attention graphs with approximately linear edges.

Abstract

from arXiv · show

Transformers-based models, such as BERT, have been one of the most successful deep learning models for NLP. Unfortunately, one of their core limitations is the quadratic dependency (mainly in terms of memory) on the sequence length due to their full attention mechanism. To remedy this, we propose, BigBird, a sparse attention mechanism that reduces this quadratic dependency to linear. We show that BigBird is a universal approximator of sequence functions and is Turing complete, thereby preserving these properties of the quadratic, full attention model. Along the way, our theoretical analysis reveals some of the benefits of having $O(1)$ global tokens (such as CLS), that attend to the entire sequence as part of the sparse attention mechanism. The proposed sparse attention can handle sequences of length up to 8x of what was previously possible using similar hardware. As a consequence of the capability to handle longer context, BigBird drastically improves performance on various NLP tasks such as question answering and summarization. We also propose novel applications to genomics data.

1 Introduction

BIGBIRD addresses the quadratic sequence-length cost of full self-attention with a linear sparse mechanism combining global, local, and random attention. It preserves key theoretical properties while supporting longer contexts and improving performance across several NLP and genomics tasks.

  • Motivation: Full self-attention has quadratic computational and memory requirements in sequence length, limiting commonly available hardware to roughly 512-token inputs.This restricts direct applicability to tasks requiring larger context, including question answering and document classification.
  • Approach: BIGBIRD combines global tokens, local neighboring-token attention, and random-token attention in a sparse mechanism with linear complexity.The approach is motivated by the need to retain contextual information while reducing the number of attention connections.
  • Empirical results: 8x longer sequence lengths are supported than previously possible using similar hardware, while the extended context benefits multiple NLP tasks.The paper reports state-of-the-art results for question answering and document summarization across multiple datasets.
  • Theory: BIGBIRD preserves theoretical expressivity: it approximates all continuous sequence-to-sequence functions with O(n) inner products and is Turing complete under standard precision assumptions.The construction uses extra tokens to retain the expressive powers of full attention.
  • Genomics: Longer masked-language-model pretraining with BIGBIRD improves downstream genomics tasks including promoter-region and chromatin-profile prediction.The paper introduces contextual representations for DNA sequences, where longer contexts are beneficial.

2 BIGBIRD Architecture

BIGBIRD represents sparse attention as a directed graph and combines random, local sliding-window, and global-token connections. Global tokens provide sequence-wide access alongside local and random context, with two construction options for their implementation.

  • Generalized attention: BIGBIRD defines attention with a directed graph whose arcs specify the query-key inner products evaluated for each output.Each query attends only to its out-neighbor set; a complete digraph recovers full quadratic attention.
  • Random attention: Random attention gives each query r randomly chosen keys, using sparse random-graph connectivity to support information flow between sequence positions.The construction is inspired by Erdős–Rényi graphs with roughly linear numbers of edges.
  • Local attention: Sliding-window attention lets a query at position i attend to neighboring keys from i − w/2 through i + w/2, capturing local structure.Locality is motivated by evidence that neighboring inner products are important in NLP tasks.
  • Global attention: Global tokens attend to all sequence tokens and receive attention from all tokens, supplying sequence-wide connections in the sparse pattern.The final mechanism combines global tokens with random and local attention.
  • Global-token constructions: BIGBIRD-ITC makes existing tokens global, whereas BIGBIRD-ETC adds extra global tokens such as CLS to store context.The two constructions differ in whether global positions are selected from the input or appended to it.

3 Theoretical Results about Sparse Attention Mechanism

BigBird shows that sparse attention can retain key expressive properties of full attention while using substantially fewer connections. Its theory establishes universal approximation and Turing completeness, while also identifying concrete costs for some tasks.

  • Expressivity: Sparse attention mechanisms can be as expressive as full attention for standalone encoders and encoder-decoder Transformers.The paper establishes universal approximation for sequence-to-sequence functions and Turing completeness under standard precision assumptions.
  • Universal Approximation: A graph containing the star graph is sufficient for universal approximation of continuous sequence-to-sequence functions.For any f in the specified continuous function class and ε > 0, a sparse-attention Transformer g exists with d_p(f, g) ≤ ε.
  • Proof Strategy: The proof constructs contextual mappings from sparse attention so feed-forward layers can assign unique outputs to input columns.A sparse shift operator uses the directed attention graph to gather sufficient contextual information despite each query attending to only a few keys.
  • Turing Completeness: Sparse attention can simulate any Turing machine using a sparse encoder and sparse decoder.The decoder-side construction adapts sparse attention to operate token by token and react only to previous tokens.
  • Limitations: A natural furthest-vector task exposes a theoretical cost of sparsity: full attention solves it in O(1) layers, whereas sufficiently sparse mechanisms require approximately Ω̃(n) layers.The lower bound applies to sparse graphs with Õ(n) edges under standard complexity-theoretic assumptions, using hardness related to the Orthogonal Vector Conjecture.

4 Experiments: Natural Language Processing

The NLP experiments test whether longer context improves masked language modeling, question answering, classification, and summarization. BIGBIRD benefits these tasks, with reported state-of-the-art results and stronger gains on longer documents.

  • Experimental scope: Longer context is evaluated for masked language modeling, question answering, document classification, and summarization.The QA setup is intended to retrieve more evidence, while long-document tasks address information distributed beyond the first 512 tokens.
  • Question answering: BIGBIRD-ETC achieves new state-of-the-art results for Natural Questions Long Answer, TriviaQA, and WikiHop, while ranking third on HotpotQA by F1.The reported test metrics are F1 for HotpotQA, Natural Questions, and TriviaQA, and accuracy for WikiHop.
  • Question answering: Both Longformer and BIGBIRD outperform models with smaller contexts on question answering.The comparison is made against the top-three leaderboard entries excluding BIGBIRD; BIGBIRD is a single model, whereas other Natural Questions entries are ensembles.
  • Classification: BIGBIRD improves the state of the art on Arxiv classification by about 5% points, while gains are not seen on the much smaller IMDb dataset.On Patents, it improves over BERT/RoBERTa but not significantly over the non-BERT state of the art.
  • Summarization: Long-document summarization uses a sparse BIGBIRD encoder with a full decoder, because input documents are much longer than output summaries.The reported experiments use three long-document datasets and evaluate summarization with ROUGE scores.

5 Experiments: Genomics

The genomics experiments apply BIGBIRD to DNA sequences by tokenizing them and learning contextual representations with masked language modeling. Fine-tuning supports promoter-region prediction and chromatin-profile prediction on non-coding genomic sequences.

  • Application: The genomics application uses longer-context masked language model pretraining for downstream promoter-region and chromatin-profile prediction.This extends attention-based contextual modeling from NLP sequences to DNA sequences.
  • Pretraining: DNA is segmented with a 32K byte-pair encoding table, producing tokens representing 8.78 base pairs on average.Contextual representations are learned on the human reference genome GRCh37 using a masked language modeling objective.
  • Promoter region prediction: BIGBIRD achieves nearly perfect promoter-region prediction accuracy, improving by 5% over the previous best reported accuracy.The model is fine-tuned to classify DNA fragments as promoter or non-promoter sequences and evaluated with F1 on the test set.
  • Chromatin-profile prediction: Chromatin-profile prediction targets large-scale chromatin profiling from non-coding genomic sequences.The task is motivated by functional effects associated with non-coding genomic variation.

6 Conclusion

BIGBIRD replaces full attention with a sparse mechanism whose complexity is linear in the number of tokens. The paper reports preserved theoretical expressivity alongside state-of-the-art NLP results and downstream genomics applications.

  • Conclusion: BIGBIRD is a sparse attention mechanism with complexity linear in the number of tokens.Its encoder retains the standard attention and fully connected network components while restricting considered attention interactions.
  • Conclusion: BIGBIRD is a universal approximator of sequence-to-sequence functions and is Turing complete.The theoretical construction uses extra global tokens to preserve expressive power.
  • Conclusion: Sparse attention incurs a cost while BIGBIRD achieves state-of-the-art performance on question answering and long-document classification.The conclusion also identifies downstream applications in promoter-region prediction and prediction of non-coding variant effects.
  • Architecture: A Transformer encoder layer combines an attention mechanism with a two-layer fully connected network, with residual additions producing each output vector.The output is expressed as z_i = O(a_i) + a_i, where a_i includes the attention output and input x_i.

A.2 Proof

The proof constructs a discretized approximation of a target sequence function after accounting for positional embeddings. It uses a grid-based approximation strategy and partitions the proof into three parts.

  • Proof structure: The proof has three parts, with the main innovation in the second part.The first and third parts largely follow standard techniques.
  • Discretization: A grid G_δ partitions the region (0, 1) at granularity δ to support approximation of the target function.The construction invokes a lemma guaranteeing a piece-wise constant approximation within ε.
  • Positional encoding: Positional embeddings are incorporated by translating the target function before applying the discretized-grid approximation.The translated function g(X) = f(X − E) is defined over position-shifted domains.
  • Reduction: The proof reduces the task to approximating a function on the encoded grid G_E.This reduction follows the construction of the position-adjusted domain.

A.2.2 Contextual Mappings and Sparse Attention Mechanisms

The construction uses sparse-attention selective shifts and a global token to encode entire contexts uniquely in token representations. Feed-forward layers then map these contextual encodings to desired sequence outputs.

  • Contextual mappings: A contextual mapping uniquely encodes each tuple of an input sequence and token representation.This encoding supports computing discretized functions from sequence context.
  • Selective shifts: Selective shift operators alter only vector entries whose inner products fall within chosen ranges.Low shifts target individual sequence columns, while high shifts target the global token.
  • Context accumulation: The proof's central lemma constructs contextual mappings by composing sparse attention layers when the graph contains a star graph.The construction maintains ordering invariants over inner products throughout the phases.
  • Context accumulation: Each phase updates one sequence column and then the global token, causing the modified column to encode the preceding context.After all phases, the global token contains a unique encoding for the input sequence.
  • Output construction: Feed-forward layers use the contextual mapping to approximate the desired output function.The resulting mapping is composed with the sparse contextual encoder to obtain the target sequence transformation.

A.2.3 Approximating modified Transformers by Transformers

The paper extends sparse-transformer expressivity from encoder mappings to encoder-decoder simulation. Sparse decoder attention preserves left-to-right computation while maintaining the information needed to simulate Turing-machine transitions.

  • Approximation: Approximating modified transformers with ReLU and softmax yields the original transformer formulation.A lemma transfers the approximation result from the modified architecture to standard transformer components.
  • Universal approximation: The sparse encoder achieves universal approximation of continuous sequence-to-sequence functions.The result applies to functions on a compact domain under the stated approximation conditions.
  • Decoder construction: The decoder combines self-attention, cross-attention, and a two-layer fully connected network at each output step.Cross-attention reads external key-value vectors from the encoder stack.
  • Turing-machine simulation: The decoder sequence maintains the simulated machine state, head symbol, and head location at each represented time step.Intermediate decoder steps aggregate relevant past symbols before producing the next machine transition.
  • Turing-machine simulation: O(n) inner products suffice for a sparse attention mechanism whose transformer networks are Turing complete.The construction simulates each step of a Turing machine using the sparse encoder-decoder architecture.
  • Decoder construction: The sparse decoder graph obeys the left-to-right constraint because no node attends to a future node.Its edge types combine locality with additional long-range connections.

C Limitations

Sparse attention does not universally replace dense attention: a task solvable by full attention in O(1) layers requires nearly linear layers for sufficiently sparse graphs under the Orthogonal Vectors Conjecture.

  • Implication: The limitation establishes a trade-off: sparse attention preserves broad expressivity but can need polynomially more layers for some global pairwise tasks.Thus sparse attention cannot universally replace dense attention.
  • Hard task: A furthest-vector task asks the model to find, for each unit vector, the vector with maximum squared distance.For unit vectors, this is equivalent to minimizing pairwise inner products.
  • Complexity assumption: The lower bound follows by reducing the task to the Orthogonal Vectors problem and invoking the Orthogonal Vectors Conjecture.With d = Θ(log^2 n), fewer than nearly linear layers would imply a subquadratic algorithm for the conjectured-hard problem.
  • Dense-versus-sparse gap: A single full-attention layer can solve the furthest-vector task by evaluating all pairwise inner products.The construction returns each input vector together with its furthest counterpart.
  • Dense-versus-sparse gap: Sparse graphs with approximately n edges require ˜Ω(n^(1−o(1))) layers for the same task under standard complexity assumptions.The lower bound applies to any sufficiently sparse attention mechanism, not only BigBird.

D Implementation details

BIGBIRD combines blockified random, local-window, and global attention, then packs sparse lookups into dense tensors for efficient accelerator computation. Its pretraining uses masked language modeling on long documents with base and large model configurations.

  • Efficient sparse computation: Sparse attention is blockified because arbitrary sparse GPU/TPU lookups and multiplications are inefficient.The implementation packs query and key blocks so operations become dense tensor multiplications.
  • Attention pattern: Each query block attends to r random key blocks, w local neighboring blocks, and g global blocks.Window attention covers indexed neighboring blocks, while global blocks attend across the sequence.
  • Efficient sparse computation: Block multiplication produces attention scores with cost O(n(g + w + r)bd) for block size b.The resulting dense score tensor is reshaped to match the BIGBIRD sparsity pattern.
  • Attention pattern: The block-attention mechanism uses block size 2, with random attention r = 1, window attention w = 3, and global attention g = 1 in its illustration.The combined model integrates the three attention components.
  • Pretraining: BIGBIRD is pretrained with masked language modeling on Books, CC-News, Stories, and Wikipedia, using base and large configurations.Documents are split or joined around length 4096, and training warm-starts from RoBERTa.
  • Pretraining: The model uses global-local attention with relative position encodings and trains global tokens using a contrastive predictive coding loss.Global-token use is learned during finetuning.

E.4 Classification

BIGBIRD is evaluated on document classification and GLUE tasks using long-context encodings and comparisons with established transformer baselines. Its gains are strongest on some longer datasets but are not uniform across tasks or baselines.

  • Document classification: BIGBIRD improves state-of-the-art performance on Arxiv by about 5% points.The classification results report F1 micro-averaged scores across datasets.
  • Document classification: On Patents, BIGBIRD improves over BERT/RoBERTa, but its improvement over non-BERT-based state of the art is not significant.The authors attribute the comparison context to the large size of the training data.
  • Document classification: BIGBIRD does not show the same performance gain on the much smaller IMDb dataset.The reported results remain competitive in the broader classification experiments.
  • GLUE: The GLUE evaluation compares BIGBIRD with BERT, XLNet, and RoBERTa across eight language-understanding tasks.The reported metrics include MCC, F1, Spearman correlation, and accuracy depending on the task.

E.5 Summarization

BIGBIRD applies sparse attention in the encoder while retaining full decoder attention for long-document summarization. On shorter datasets, its performance is competitive with models using full attention.

  • Model configuration: Sparse BIGBIRD attention is used only in the encoder, while the decoder retains full attention because output sequences are short.The encoder and decoder use the same hidden layers, heads, and hidden dimension.
  • Evaluation: The summarization experiments cover three long-document datasets and separately evaluate two shorter datasets.Dataset statistics are provided for both long and short-document settings.
  • Model configuration: The encoder-decoder model is warm-started from pretrained weights, with weights shared between encoder and decoder.The base model uses MLM-pretrained BIGBIRD weights, while the large model uses Pegasus weights.
  • Results: On shorter datasets, BIGBIRD performance is competitive with full-attention models.This experiment tests whether sparse attention causes significant degradation when full attention is feasible.

F Genomics experiments details

The genomics experiments adapt BIGBIRD to long DNA contexts through document construction, tokenization, masked language modeling, and downstream prediction tasks. They evaluate promoter recognition and chromatin-profile prediction using human GRCh37 sequences.

  • Data construction: Genomics documents are built from consecutive DNA fragments, with 50–100 sentences of 500–1000 base pairs each.Each resulting document contains 25,000–100,000 base pairs, and the procedure produces approximately 450K documents.
  • Pretraining: SentencePiece tokenization uses five-character building blocks and a 32k byte-pair encoding vocabulary.Each token represents 8.78 base pairs on average.
  • Pretraining: BIGBIRD pretraining follows BERT-style masked language modeling and next sentence prediction objectives.MLM masks 15% of tokens, while NSP predicts whether sequence pairs are contiguous.
  • Promoter region prediction: Promoter prediction uses 8,000-base-pair sequences around transcription start sites from the human reference genome.Positive and constructed negative examples are prefixed and appended with [CLS] and [SEP].
  • Chromatin profile prediction: Chromatin-profile prediction uses 8,000-base-pair GRCh37 sequences centered on 200-base-pair bins and predicts 919 chromatin features jointly.The labels include transcription-factor, DNase I sensitivity, and histone-mark profiles.
  • Chromatin profile prediction: Chromatin prediction holds out chromosomes 8 and 9 for testing and uses chromosome 7 samples for validation.The training and testing split is chromosome-based and strictly non-overlapping.
Loading 2007.14062v2…