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

arXiv: https://arxiv.org/abs/1911.04070 · HTML: https://mlsanity.com/paper/1911.04070/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Nov 2019.

## Built on by (most cited first, 30 of 38)

- [Perceiver: General Perception with Iterative Attention](https://mlsanity.com/paper/2103.03206/) (2021)
- [A Survey of Transformers](https://mlsanity.com/paper/2106.04554/) (2021)
- [Long-Short Transformer: Efficient Transformers for Language and Vision](https://mlsanity.com/paper/2107.02192/) (2021)
- [Hierarchical Transformers Are More Efficient Language Models](https://mlsanity.com/paper/2110.13711/) (2021)
- [Advancing Transformer Architecture in Long-Context Large Language Models: A Comprehensive Survey](https://mlsanity.com/paper/2311.12351/) (2023)
- [Model Compression and Efficient Inference for Large Language Models: A Survey](https://mlsanity.com/paper/2402.09748/) (2024)
- [Poolingformer: Long Document Modeling with Pooling Attention](https://mlsanity.com/paper/2105.04371/) (2021)
- [Memory-efficient Transformers via Top-k Attention](https://mlsanity.com/paper/2106.06899/) (2021)
- [Museformer: Transformer with Fine- and Coarse-Grained Attention for Music Generation](https://mlsanity.com/paper/2210.10349/) (2022)
- [Long-Range Transformers for Dynamic Spatiotemporal Forecasting](https://mlsanity.com/paper/2109.12218/) (2021)
- [Log-Linear Attention](https://mlsanity.com/paper/2506.04761/) (2025)
- [Foundation Models for Music: A Survey](https://mlsanity.com/paper/2408.14340/) (2024)
- [Hierarchical Learning for Generation with Long Source Sequences](https://mlsanity.com/paper/2104.07545/) (2021)
- [Not All Memories are Created Equal: Learning to Forget by Expiring](https://mlsanity.com/paper/2105.06548/) (2021)
- [GNN-LM: Language Modeling based on Global Contexts via GNN](https://mlsanity.com/paper/2110.08743/) (2021)
- [Transformer-VQ: Linear-Time Transformers via Vector Quantization](https://mlsanity.com/paper/2309.16354/) (2023)
- [A Length Adaptive Algorithm-Hardware Co-design of Transformer on FPGA Through Sparse Attention and Dynamic Pipelining](https://mlsanity.com/paper/2208.03646/) (2022)
- [Extending LLMs' Context Window with 100 Samples](https://mlsanity.com/paper/2401.07004/) (2024)
- [On Learning the Transformer Kernel](https://mlsanity.com/paper/2110.08323/) (2021)
- [Pyramid-BERT: Reducing Complexity via Successive Core-set based Token Selection](https://mlsanity.com/paper/2203.14380/) (2022)
- [Sparse Attention Acceleration with Synergistic In-Memory Pruning and On-Chip Recomputation](https://mlsanity.com/paper/2209.00606/) (2022)
- [Efficient Heterogeneous Large Language Model Decoding with Model-Attention Disaggregation](https://mlsanity.com/paper/2405.01814/) (2024)
- [Large Human Language Models: A Need and the Challenges](https://mlsanity.com/paper/2312.07751/) (2023)
- [StreamingDialogue: Prolonged Dialogue Learning via Long Context Compression with Minimal Losses](https://mlsanity.com/paper/2403.08312/) (2024)
- [Accelerating Attention through Gradient-Based Learned Runtime Pruning](https://mlsanity.com/paper/2204.03227/) (2022)
- [Value-aware Approximate Attention](https://mlsanity.com/paper/2103.09857/) (2021)
- [What Helps Transformers Recognize Conversational Structure? Importance of Context, Punctuation, and Labels in Dialog Act Recognition](https://mlsanity.com/paper/2107.02294/) (2021)
- [Infomaxformer: Maximum Entropy Transformer for Long Time-Series Forecasting Problem](https://mlsanity.com/paper/2301.01772/) (2023)
- [Sparse Fusion for Multimodal Transformers](https://mlsanity.com/paper/2111.11992/) (2021)
- [Efficient Beam Tree Recursion](https://mlsanity.com/paper/2307.10779/) (2023)

## Abstract (arXiv)

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· nlog (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.