# You Only Sample (Almost) Once: Linear Cost Self-Attention Via Bernoulli Sampling

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 46 references that are in the map.
- First posted on arXiv 18 Nov 2021.

## Builds on (most cited first, 30 of 30)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://mlsanity.com/paper/1909.11942/) (2019)
- [A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference](https://mlsanity.com/paper/1704.05426/) (2017)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Aligning Books and Movies: Towards Story-like Visual Explanations by Watching Movies and Reading Books](https://mlsanity.com/paper/1506.06724/) (2015)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Defending Against Neural Fake News](https://mlsanity.com/paper/1905.12616/) (2019)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [A Simple Method for Commonsense Reasoning](https://mlsanity.com/paper/1806.02847/) (2018)
- [Constructing Datasets for Multi-hop Reading Comprehension Across Documents](https://mlsanity.com/paper/1710.06481/) (2017)
- [ListOps: A Diagnostic Dataset for Latent Tree Learning](https://mlsanity.com/paper/1804.06028/) (2018)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Learning long-range spatial dependencies with horizontal gated-recurrent units](https://mlsanity.com/paper/1805.08315/) (2018)
- [Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers](https://mlsanity.com/paper/2006.03555/) (2020)
- [Hashing-Based-Estimators for Kernel Density in High Dimensions](https://mlsanity.com/paper/1808.10530/) (2018)
- [On Symmetric and Asymmetric LSHs for Inner Product Search](https://mlsanity.com/paper/1410.5518/) (2014)
- [A New Unbiased and Efficient Class of LSH-Based Samplers and Estimators for Partition Function Computation in Log-Linear Models](https://mlsanity.com/paper/1703.05160/) (2017)

## Built on by (most cited first, 17 of 17)

- [Deep Unlearning via Randomized Conditionally Independent Hessians](https://mlsanity.com/paper/2204.07655/) (2022)
- [Flowformer: Linearizing Transformers with Conservation Flows](https://mlsanity.com/paper/2202.06258/) (2022)
- [Attention Mechanism in Neural Networks: Where it Comes and Where it Goes](https://mlsanity.com/paper/2204.13154/) (2022)
- [Primal-Attention: Self-attention through Asymmetric Kernel SVD in Primal Representation](https://mlsanity.com/paper/2305.19798/) (2023)
- [Sampling Is All You Need on Modeling Long-Term User Behaviors for CTR Prediction](https://mlsanity.com/paper/2205.10249/) (2022)
- [Multi Resolution Analysis (MRA) for Approximate Self-Attention](https://mlsanity.com/paper/2207.10284/) (2022)
- [Graph Convolutions Enrich the Self-Attention in Transformers!](https://mlsanity.com/paper/2312.04234/) (2023)
- [CAB: Comprehensive Attention Benchmarking on Long Sequence Modeling](https://mlsanity.com/paper/2210.07661/) (2022)
- [When Linear Attention Meets Autoregressive Decoding: Towards More Effective and Efficient Linearized Large Language Models](https://mlsanity.com/paper/2406.07368/) (2024)
- [LookupFFN: Making Transformers Compute-lite for CPU inference](https://mlsanity.com/paper/2403.07221/) (2024)
- [Vcc: Scaling Transformers to 128K Tokens or More by Prioritizing Important Tokens](https://mlsanity.com/paper/2305.04241/) (2023)
- [MemoryFormer: Minimize Transformer Computation by Removing Fully-Connected Layers](https://mlsanity.com/paper/2411.12992/) (2024)
- [RACE Attention: A Strictly Linear-Time Attention Layer for Training on Outrageously Large Contexts](https://mlsanity.com/paper/2510.04008/) (2025)
- [DBA: Efficient Transformer with Dynamic Bilinear Low-Rank Attention](https://mlsanity.com/paper/2211.16368/) (2022)
- [From Characters to Words: Hierarchical Pre-trained Language Model for Open-vocabulary Language Understanding](https://mlsanity.com/paper/2305.14571/) (2023)
- [Learning Advanced Self-Attention for Linear Transformers in the Singular Value Domain](https://mlsanity.com/paper/2505.08516/) (2025)
- [Computation and Parameter Efficient Multi-Modal Fusion Transformer for Cued Speech Recognition](https://mlsanity.com/paper/2401.17604/) (2024)

## Abstract (arXiv)

Transformer-based models are widely used in natural language processing (NLP). Central to the transformer model is the self-attention mechanism, which captures the interactions of token pairs in the input sequences and depends quadratically on the sequence length. Training such models on longer sequences is expensive. In this paper, we show that a Bernoulli sampling attention mechanism based on Locality Sensitive Hashing (LSH), decreases the quadratic complexity of such models to linear. We bypass the quadratic cost by considering self-attention as a sum of individual tokens associated with Bernoulli random variables that can, in principle, be sampled at once by a single hash (although in practice, this number may be a small constant). This leads to an efficient sampling scheme to estimate self-attention which relies on specific modifications of LSH (to enable deployment on GPU architectures). We evaluate our algorithm on the GLUE benchmark with standard 512 sequence length where we see favorable performance relative to a standard pretrained Transformer. On the Long Range Arena (LRA) benchmark, for evaluating performance on long sequences, our method achieves results consistent with softmax self-attention but with sizable speed-ups and memory savings and often outperforms other efficient self-attention methods. Our code is available at https://github.com/mlpen/YOSO