# Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 55 references that are in the map.
- First posted on arXiv 10 Dec 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting](https://mlsanity.com/paper/2012.07436/) (2020)
- [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)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth](https://mlsanity.com/paper/2103.03404/) (2021)
- [Efficient Attentions for Long Document Summarization](https://mlsanity.com/paper/2104.02112/) (2021)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Blockwise Self-Attention for Long Document Understanding](https://mlsanity.com/paper/1911.02972/) (2019)
- [Document-Level Event Argument Extraction by Conditional Generation](https://mlsanity.com/paper/2104.05919/) (2021)
- [ListOps: A Diagnostic Dataset for Latent Tree Learning](https://mlsanity.com/paper/1804.06028/) (2018)
- [Learning long-range spatial dependencies with horizontal gated-recurrent units](https://mlsanity.com/paper/1805.08315/) (2018)
- [Multi-Sentence Argument Linking](https://mlsanity.com/paper/1911.03766/) (2019)
- [Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Method](https://mlsanity.com/paper/2111.00035/) (2021)
- [Extractive Summarization of Long Documents by Combining Global and Local Context](https://mlsanity.com/paper/1909.08089/) (2019)
- [G-Transformer for Document-level Machine Translation](https://mlsanity.com/paper/2105.14761/) (2021)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Randomized sketches for kernels: Fast and optimal non-parametric regression](https://mlsanity.com/paper/1501.06195/) (2015)
- [Document-Level Event Role Filler Extraction using Multi-Granularity Contextualized Encoding](https://mlsanity.com/paper/2005.06579/) (2020)

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

- [LM-Infinite: Zero-Shot Extreme Length Generalization for Large Language Models](https://mlsanity.com/paper/2308.16137/) (2023)
- [Towards LifeSpan Cognitive Systems](https://mlsanity.com/paper/2409.13265/) (2024)
- [Even Sparser Graph Transformers](https://mlsanity.com/paper/2411.16278/) (2024)
- [WildCat: Near-Linear Attention in Theory and Practice](https://mlsanity.com/paper/2602.10056/) (2026)
- [Accelerating Attention with Basis Decomposition](https://mlsanity.com/paper/2510.01718/) (2025)

## Abstract (arXiv)

Transformer-based models are not efficient in processing long sequences due to the quadratic space and time complexity of the self-attention modules. To address this limitation, Linformer and Informer are proposed to reduce the quadratic complexity to linear (modulo logarithmic factors) via low-dimensional projection and row selection respectively. These two models are intrinsically connected, and to understand their connection, we introduce a theoretical framework of matrix sketching. Based on the theoretical analysis, we propose Skeinformer to accelerate self-attention and further improve the accuracy of matrix approximation to self-attention with three carefully designed components: column sampling, adaptive row normalization and pilot sampling reutilization. Experiments on the Long Range Arena (LRA) benchmark demonstrate that our methods outperform alternatives with a consistently smaller time/space footprint.