# Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Method

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 51 references that are in the map.
- First posted on arXiv 29 Oct 2021.

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

- [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)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension](https://mlsanity.com/paper/1910.13461/) (2019)
- [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)
- [TinyBERT: Distilling BERT for Natural Language Understanding](https://mlsanity.com/paper/1909.10351/) (2019)
- [Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Pruned](https://mlsanity.com/paper/1905.09418/) (2019)
- [Are Sixteen Heads Really Better than One?](https://mlsanity.com/paper/1905.10650/) (2019)
- [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)
- [FastBERT: a Self-distilling BERT with Adaptive Inference Time](https://mlsanity.com/paper/2004.02178/) (2020)
- [Understanding the Difficulty of Training Transformers](https://mlsanity.com/paper/2004.08249/) (2020)
- [Synthesizer: Rethinking Self-Attention in Transformer Models](https://mlsanity.com/paper/2005.00743/) (2020)
- [Blockwise Self-Attention for Long Document Understanding](https://mlsanity.com/paper/1911.02972/) (2019)
- [Distilling Task-Specific Knowledge from BERT into Simple Neural Networks](https://mlsanity.com/paper/1903.12136/) (2019)
- [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)
- [Low-Rank Bottleneck in Multi-head Attention Models](https://mlsanity.com/paper/2002.07028/) (2020)

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

- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [LM-Infinite: Zero-Shot Extreme Length Generalization for Large Language Models](https://mlsanity.com/paper/2308.16137/) (2023)
- [The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicry](https://mlsanity.com/paper/2402.04347/) (2024)
- [The Devil in Linear Transformer](https://mlsanity.com/paper/2210.10340/) (2022)
- [KERPLE: Kernelized Relative Positional Embedding for Length Extrapolation](https://mlsanity.com/paper/2205.09921/) (2022)
- [Test-time regression: a unifying framework for designing sequence models with associative memory](https://mlsanity.com/paper/2501.12352/) (2025)
- [KDEformer: Accelerating Transformers via Kernel Density Estimation](https://mlsanity.com/paper/2302.02451/) (2023)
- [Toeplitz Neural Network for Sequence Modeling](https://mlsanity.com/paper/2305.04749/) (2023)
- [In-Context Learning with Many Demonstration Examples](https://mlsanity.com/paper/2302.04931/) (2023)
- [Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Models](https://mlsanity.com/paper/2404.03827/) (2024)
- [PolaFormer: Polarity-aware Linear Attention for Vision Transformers](https://mlsanity.com/paper/2501.15061/) (2025)
- [Linear Complexity Randomized Self-attention Mechanism](https://mlsanity.com/paper/2204.04667/) (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)
- [LoLCATs: On Low-Rank Linearizing of Large Language Models](https://mlsanity.com/paper/2410.10254/) (2024)
- [Encryption-Friendly LLM Architecture](https://mlsanity.com/paper/2410.02486/) (2024)
- [Towards LifeSpan Cognitive Systems](https://mlsanity.com/paper/2409.13265/) (2024)
- [Linear Log-Normal Attention with Unbiased Concentration](https://mlsanity.com/paper/2311.13541/) (2023)
- [Unraveling the Gradient Descent Dynamics of Transformers](https://mlsanity.com/paper/2411.07538/) (2024)
- [CAB: Comprehensive Attention Benchmarking on Long Sequence Modeling](https://mlsanity.com/paper/2210.07661/) (2022)
- [ZETA: Leveraging Z-order Curves for Efficient Top-k Attention](https://mlsanity.com/paper/2501.14577/) (2025)
- [Exploring Transformer Extrapolation](https://mlsanity.com/paper/2307.10156/) (2023)
- [Revisiting associative recall in modern recurrent models](https://mlsanity.com/paper/2508.19029/) (2025)
- [Empowering parameter-efficient transfer learning by recognizing the kernel structure in self-attention](https://mlsanity.com/paper/2205.03720/) (2022)
- [WildCat: Near-Linear Attention in Theory and Practice](https://mlsanity.com/paper/2602.10056/) (2026)
- [Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences](https://mlsanity.com/paper/2112.05359/) (2021)
- [Calibrate and Debias Layer-wise Sampling for Graph Convolutional Networks](https://mlsanity.com/paper/2206.00583/) (2022)
- [Fast-FNet: Accelerating Transformer Encoder Models via Efficient Fourier Layers](https://mlsanity.com/paper/2209.12816/) (2022)
- [Investigating Recurrent Transformers with Dynamic Halt](https://mlsanity.com/paper/2402.00976/) (2024)
- [Spectraformer: A Unified Random Feature Framework for Transformer](https://mlsanity.com/paper/2405.15310/) (2024)

## Abstract (arXiv)

Transformers are expensive to train due to the quadratic time and space complexity in the self-attention mechanism. On the other hand, although kernel machines suffer from the same computation bottleneck in pairwise dot products, several approximation schemes have been successfully incorporated to considerably reduce their computational cost without sacrificing too much accuracy. In this work, we leverage the computation methods for kernel machines to alleviate the high computational cost and introduce Skyformer, which replaces the softmax structure with a Gaussian kernel to stabilize the model training and adapts the Nystr"om method to a non-positive semidefinite matrix to accelerate the computation. We further conduct theoretical analysis by showing that the matrix approximation error of our proposed method is small in the spectral norm. Experiments on Long Range Arena benchmark show that the proposed method is sufficient in getting comparable or even better performance than the full self-attention while requiring fewer computation resources.