# Transformers are Multi-State RNNs

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

## Key facts

- Cited by 120 papers in the map (data through 14 Oct 2026).
- Placed in Early exit and edge inference, one of 12 directions in Efficient LLM inference and serving.
- Builds on 36 of its 64 references that are in the map.
- First posted on arXiv 11 Jan 2024.

## Placed in

- Efficient LLM inference and serving / [Early exit and edge inference](https://mlsanity.com/inference/early-exit-and-edge-inference/)

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [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)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [LIMA: Less Is More for Alignment](https://mlsanity.com/paper/2305.11206/) (2023)
- [Large Language Models are not Fair Evaluators](https://mlsanity.com/paper/2305.17926/) (2023)
- [What Does BERT Look At? An Analysis of BERT's Attention](https://mlsanity.com/paper/1906.04341/) (2019)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [Are Sixteen Heads Really Better than One?](https://mlsanity.com/paper/1905.10650/) (2019)
- [Extending Context Window of Large Language Models via Positional Interpolation](https://mlsanity.com/paper/2306.15595/) (2023)
- [Compressive Transformers for Long-Range Sequence Modelling](https://mlsanity.com/paper/1911.05507/) (2019)
- [Gated Linear Attention Transformers with Hardware-Efficient Training](https://mlsanity.com/paper/2312.06635/) (2023)
- [A Dataset of Information-Seeking Questions and Answers Anchored in Research Papers](https://mlsanity.com/paper/2105.03011/) (2021)
- [Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs](https://mlsanity.com/paper/2310.01801/) (2023)
- [Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time](https://mlsanity.com/paper/2305.17118/) (2023)
- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [Pay Attention to MLPs](https://mlsanity.com/paper/2105.08050/) (2021)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [FNet: Mixing Tokens with Fourier Transforms](https://mlsanity.com/paper/2105.03824/) (2021)
- [Unitary Evolution Recurrent Neural Networks](https://mlsanity.com/paper/1511.06464/) (2015)
- [Long Range Language Modeling via Gated State Spaces](https://mlsanity.com/paper/2206.13947/) (2022)
- [ZeroSCROLLS: A Zero-Shot Benchmark for Long Text Understanding](https://mlsanity.com/paper/2305.14196/) (2023)
- [Primer: Searching for Efficient Transformers for Language Modeling](https://mlsanity.com/paper/2109.08668/) (2021)
- [Multi-passage BERT: A Globally Normalized BERT Model for Open-domain Question Answering](https://mlsanity.com/paper/1908.08167/) (2019)

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

- [MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention](https://mlsanity.com/paper/2407.02490/) (2024)
- [MoBA: Mixture of Block Attention for Long-Context LLMs](https://mlsanity.com/paper/2502.13189/) (2025)
- [Dynamic Memory Compression: Retrofitting LLMs for Accelerated Inference](https://mlsanity.com/paper/2403.09636/) (2024)
- [Keep the Cost Down: A Review on Methods to Optimize LLM' s KV-Cache Consumption](https://mlsanity.com/paper/2407.18003/) (2024)
- [KVzip: Query-Agnostic KV Cache Compression with Context Reconstruction](https://mlsanity.com/paper/2505.23416/) (2025)
- [Cartridges: Lightweight and general-purpose long context representations via self-study](https://mlsanity.com/paper/2506.06266/) (2025)
- [Get More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inference](https://mlsanity.com/paper/2402.09398/) (2024)
- [Expected Attention: KV Cache Compression by Estimating Attention from Future Queries Distribution](https://mlsanity.com/paper/2510.00636/) (2025)
- [Found in the Middle: How Language Models Use Long Contexts Better via Plug-and-Play Positional Encoding](https://mlsanity.com/paper/2403.04797/) (2024)
- [KVLink: Accelerating Large Language Models via Efficient KV Cache Reuse](https://mlsanity.com/paper/2502.16002/) (2025)
- [CAKE: Cascading and Adaptive KV Cache Eviction with Layer Preferences](https://mlsanity.com/paper/2503.12491/) (2025)
- [Squeezed Attention: Accelerating Long Context Length LLM Inference](https://mlsanity.com/paper/2411.09688/) (2024)
- [KeyDiff: Key Similarity-Based KV Cache Eviction for Long-Context LLM Inference in Resource-Constrained Environments](https://mlsanity.com/paper/2504.15364/) (2025)
- [LServe: Efficient Long-sequence LLM Serving with Unified Sparse Attention](https://mlsanity.com/paper/2502.14866/) (2025)
- [Understanding the differences in Foundation Models: Attention, State Space Models, and Recurrent Neural Networks](https://mlsanity.com/paper/2405.15731/) (2024)
- [TransformerFAM: Feedback attention is working memory](https://mlsanity.com/paper/2404.09173/) (2024)
- [Memory-Efficient Visual Autoregressive Modeling with Scale-Aware KV Cache Compression](https://mlsanity.com/paper/2505.19602/) (2025)
- [AudioMarathon: A Comprehensive Benchmark for Long-Context Audio Understanding and Efficiency in Audio LLMs](https://mlsanity.com/paper/2510.07293/) (2025)
- [TriAttention: Efficient Long Reasoning with Trigonometric KV Compression](https://mlsanity.com/paper/2604.04921/) (2026)
- [Efficient Autoregressive Video Diffusion with Dummy Head](https://mlsanity.com/paper/2601.20499/) (2026)
- [Reasoning Path Compression: Compressing Generation Trajectories for Efficient LLM Reasoning](https://mlsanity.com/paper/2505.13866/) (2025)
- [Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores](https://mlsanity.com/paper/2507.08143/) (2025)
- [LazyEviction: Lagged KV Eviction with Attention Pattern Observation for Efficient Long Reasoning](https://mlsanity.com/paper/2506.15969/) (2025)
- [Multipole Attention for Efficient Long Context Reasoning](https://mlsanity.com/paper/2506.13059/) (2025)
- [Taming the Fragility of KV Cache Eviction in LLM Inference](https://mlsanity.com/paper/2510.13334/) (2025)
- [Learning to Evict from Key-Value Cache](https://mlsanity.com/paper/2602.10238/) (2026)
- [Towards LifeSpan Cognitive Systems](https://mlsanity.com/paper/2409.13265/) (2024)
- [In-context KV-Cache Eviction for LLMs via Attention-Gate](https://mlsanity.com/paper/2410.12876/) (2024)
- [CAOTE: KV Cache Selection for LLMs via Attention Output Error-Based Token Eviction](https://mlsanity.com/paper/2504.14051/) (2025)
- [KV Cache Transform Coding for Compact Storage in LLM Inference](https://mlsanity.com/paper/2511.01815/) (2025)

## Abstract (arXiv)

Transformers are considered conceptually different from the previous generation of state-of-the-art NLP models - recurrent neural networks (RNNs). In this work, we demonstrate that decoder-only transformers can in fact be conceptualized as unbounded multi-state RNNs - an RNN variant with unlimited hidden state size. We further show that transformers can be converted into textitbounded multi-state RNNs by fixing the size of their hidden state, effectively compressing their key-value cache. We introduce a novel, training-free compression policy - Token Omission Via Attention (TOVA). Our experiments with four long range tasks and several LLMs show that TOVA outperforms several baseline compression policies. Particularly, our results are nearly on par with the full model, using in some cases only frac18 of the original cache size, which translates to 4.8X higher throughput. Our results shed light on the connection between transformers and RNNs, and help mitigate one of LLMs' most painful computational bottlenecks - the size of their key-value cache. We publicly release our code at https://github.com/schwartz-lab-NLP/TOVA