# Luna: Linear Unified Nested Attention

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

## Key facts

- Cited by 96 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 59 references that are in the map.
- First posted on arXiv 3 Jun 2021.

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

- [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)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [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)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge](https://mlsanity.com/paper/1811.00937/) (2018)
- [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)
- [fairseq: A Fast, Extensible Toolkit for Sequence Modeling](https://mlsanity.com/paper/1904.01038/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)](https://mlsanity.com/paper/1511.07289/) (2015)
- [Aligning Books and Movies: Towards Story-like Visual Explanations by Watching Movies and Reading Books](https://mlsanity.com/paper/1506.06724/) (2015)
- [On Layer Normalization in the Transformer Architecture](https://mlsanity.com/paper/2002.04745/) (2020)
- [RACE: Large-scale ReAding Comprehension Dataset From Examinations](https://mlsanity.com/paper/1704.04683/) (2017)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Image Transformer](https://mlsanity.com/paper/1802.05751/) (2018)
- [Compressive Transformers for Long-Range Sequence Modelling](https://mlsanity.com/paper/1911.05507/) (2019)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [Q-BERT: Hessian Based Ultra Low Precision Quantization of BERT](https://mlsanity.com/paper/1909.05840/) (2019)

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

- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Perceiver IO: A General Architecture for Structured Inputs & Outputs](https://mlsanity.com/paper/2107.14795/) (2021)
- [Harnessing the Power of LLMs in Practice: A Survey on ChatGPT and Beyond](https://mlsanity.com/paper/2304.13712/) (2023)
- [A Survey of Transformers](https://mlsanity.com/paper/2106.04554/) (2021)
- [LongT5: Efficient Text-To-Text Transformer for Long Sequences](https://mlsanity.com/paper/2112.07916/) (2021)
- [A Survey on Efficient Inference for Large Language Models](https://mlsanity.com/paper/2404.14294/) (2024)
- [LongNet: Scaling Transformers to 1,000,000,000 Tokens](https://mlsanity.com/paper/2307.02486/) (2023)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Mega: Moving Average Equipped Gated Attention](https://mlsanity.com/paper/2209.10655/) (2022)
- [FLatten Transformer: Vision Transformer using Focused Linear Attention](https://mlsanity.com/paper/2308.00442/) (2023)
- [Self-attention Does Not Need O(n2) Memory](https://mlsanity.com/paper/2112.05682/) (2021)
- [Liquid Structural State-Space Models](https://mlsanity.com/paper/2209.12951/) (2022)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [MiniCache: KV Cache Compression in Depth Dimension for Large Language Models](https://mlsanity.com/paper/2405.14366/) (2024)
- [A Survey of Resource-efficient LLM and Multimodal Foundation Models](https://mlsanity.com/paper/2401.08092/) (2024)
- [Gated Slot Attention for Efficient Linear-Time Sequence Modeling](https://mlsanity.com/paper/2409.07146/) (2024)
- [Diffusion Models Without Attention](https://mlsanity.com/paper/2311.18257/) (2023)
- [Advancing Transformer Architecture in Long-Context Large Language Models: A Comprehensive Survey](https://mlsanity.com/paper/2311.12351/) (2023)
- [Efficient Long-Text Understanding with Short-Text Models](https://mlsanity.com/paper/2208.00748/) (2022)
- [Mamba-360: Survey of State Space Models as Transformer Alternative for Long Sequence Modelling: Methods, Applications, and Challenges](https://mlsanity.com/paper/2404.16112/) (2024)
- [General-purpose, long-context autoregressive modeling with Perceiver AR](https://mlsanity.com/paper/2202.07765/) (2022)
- [Joint Global and Local Hierarchical Priors for Learned Image Compression](https://mlsanity.com/paper/2112.04487/) (2021)
- [BAMBOO: A Comprehensive Benchmark for Evaluating Long Text Modeling Capacities of Large Language Models](https://mlsanity.com/paper/2309.13345/) (2023)
- [Linearizing Large Language Models](https://mlsanity.com/paper/2405.06640/) (2024)
- [A Survey on Long Text Modeling with Transformers](https://mlsanity.com/paper/2302.14502/) (2023)
- [Megalodon: Efficient LLM Pretraining and Inference with Unlimited Context Length](https://mlsanity.com/paper/2404.08801/) (2024)
- [Adaptive Frequency Filters As Efficient Global Token Mixers](https://mlsanity.com/paper/2307.14008/) (2023)
- [Diffusion-RWKV: Scaling RWKV-Like Architectures for Diffusion Models](https://mlsanity.com/paper/2404.04478/) (2024)

## Abstract (arXiv)

The quadratic computational and memory complexities of the Transformer's attention mechanism have limited its scalability for modeling long sequences. In this paper, we propose Luna, a linear unified nested attention mechanism that approximates softmax attention with two nested linear attention functions, yielding only linear (as opposed to quadratic) time and space complexity. Specifically, with the first attention function, Luna packs the input sequence into a sequence of fixed length. Then, the packed sequence is unpacked using the second attention function. As compared to a more traditional attention mechanism, Luna introduces an additional sequence with a fixed length as input and an additional corresponding output, which allows Luna to perform attention operation linearly, while also storing adequate contextual information. We perform extensive evaluations on three benchmarks of sequence modeling tasks: long-context sequence modeling, neural machine translation and masked language modeling for large-scale pretraining. Competitive or even better experimental results demonstrate both the effectiveness and efficiency of Luna compared to a variety