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

Abstract

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.

References in corpus (7)

• Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
• Generating Long Sequences with Sparse Transformers
• Neural Machine Translation in Linear Time
• When Are Tree Structures Necessary for Deep Learning of Representations?
• Multiplicative LSTM for sequence modelling
• Bi-Directional Block Self-Attention for Fast and Memory-Efficient Sequence Modeling
• Hierarchical Transformers for Multi-Document Summarization

Cited by in corpus (19)

• Longformer: The Long-Document Transformer
• Big Bird: Transformers for Longer Sequences
• Perceiver: General Perception with Iterative Attention
• Long-Range Transformers for Dynamic Spatiotemporal Forecasting
• Long-Short Transformer: Efficient Transformers for Language and Vision
• A Length Adaptive Algorithm-Hardware Co-design of Transformer on FPGA Through Sparse Attention and Dynamic Pipelining
• Hierarchical Learning for Generation with Long Source Sequences
• Multi-Graph Transformer for Free-Hand Sketch Recognition
• ETC: Encoding Long and Structured Inputs in Transformers
• GMAT: Global Memory Augmentation for Transformers
• Zero-shot Entity Linking with Efficient Long Range Sequence Modeling
• GNN-LM: Language Modeling based on Global Contexts via GNN
• SAC: Accelerating and Structuring Self-Attention via Sparse Adaptive Connection
• ERNIE-Doc: A Retrospective Long-Document Modeling Transformer
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers
• Summarize, Outline, and Elaborate: Long-Text Generation via Hierarchical Supervision from Extractive Summaries
• Which *BERT? A Survey Organizing Contextualized Encoders
• Not All Memories are Created Equal: Learning to Forget by Expiring
• Transformer on a Diet