BP-Transformer: Modelling Long-Range Context via Binary Partitioning

By Zihao Ye, Qipeng Guo, Quan Gan, Xipeng Qiu, Zheng Zhang. 2019

85 citations recorded by the source corpus.

The Transformer model is widely successful on many natural language processing tasks. However, the quadratic complexity of self-attention limit its application on long text. In this paper, adopting a fine-to-coarse attention mechanism on multi-scale spans via binary partitioning (BP), we propose BP-Transformer (BPT for short). BPT yields $O(k\cdot n\log (n/k))$ connections where $k$ is a hyperparameter to control the density of attention. BPT has a good balance between computation complexity and model capacity. A series of experiments on text classification, machine translation and language modeling shows BPT has a superior performance for long text than previous self-attention models. Our code, hyperparameters and CUDA kernels for sparse attention are available in PyTorch.

Subfields: Artificial Intelligence, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Model Architectures

Citations in the corpus

Big Bird: Transformers for Longer Sequences (2020, methodology): “Ye et al. [104] proposed binary partitions of the data where as Qiu et al. [73] reduced complexity by using block sparsity.”
Longformer: The Long-Document Transformer (2020, methodology): “…having the (Dai et al., 2019) 41M - 1.06 Reformer (Kitaev et al., 2020) - - 1.05 Adaptive (Sukhbaatar et al., 2019) 39M 1.04 1.02 BP-Transformer (Ye et al., 2019) 38M - 1.02 Our Longformer 41M 1.02 1.00 We do not use dilated sliding windows for lower layers to maximize their capacity to learn…”
ETC: Encoding Long and Structured Inputs in Transformers (2020, methodology): “The BP-Transformer (Ye et al., 2019) model builds a binary partitioning tree over the input, and only lets the model attend to the leaves (the raw tokens) for nearby tokens, and higher nodes in the tree (summaries of groups of tokens) as tokens grow more distant (see Figure 1, middle top).”
ETC: Encoding Long and Structured Data in Transformers (2020, methodology): “For example, the BP-Transformer (Ye et al., 2019) model builds a binary partitioning tree over the input, and only lets the model attend to the leaves (the raw”
$O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers (2020, methodology): “To mitigate this issue, researchers have developed methods to sparsify the pairwise interactions/connections in self-attention layers to reduce the computational complexity and/or improve model interpretability, and have shown successful empirical results on tasks with long sequence lengths [2, 6, 8”
GMAT: Global Memory Augmentation for Transformers (2020, methodology): “To alleviate this issue, several sparsifications of vanilla self-attention have been recently proposed; each restricting the number of positions that a given position can attend to [28, 2, 21, 30, 20, 9, 1].”
A Survey of Transformers (2021, methodology): “For text data, BP-Transformer [158] constructs a binary tree where all tokens are leaf nodes and the internal nodes are span nodes containing many tokens.”