Transformers are Multi-State RNNs
Open accessAbstract
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 $\textit{bounded}$ 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 - $\textbf{T}$oken $\textbf{O}$mission $\textbf{V}$ia $\textbf{A}$ttention (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 $\frac{1}{8}$ 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
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Existing context-compression methods often use distillation to produce an offline prompt, memory, or compressed KV representation before generation.
“Existing context-compression methods often use distillation to produce an offline prompt, memory, or compressed KV representation before generation [7, 28, 53, 32, 19, 34, 56, 30, 31].”
From Learning What to Remember: Test-Time Training via Context Distillation (2026) · cites this paper as [34]
Section 7.1 says the paper’s TOVA method compresses cached K and V matrices during autoregressive decoding. Section 5.1 describes baseline policies that require no additional training. The paper therefore supports the compressed-KV part of the sentence, but not the attributed use of distillation to produce an offline representation before generation. (LLM, conf=0.85)
Experimental — accuracy not yet measuredTOVA uses the final token's attention.
“TOVA (Oren et al., 2024) uses the final token's attention”
From How Query Visibility Changes KV-Cache Compression Rankings: A Matched-Budget Audit (2026) · cites this paper as Oren et al., 2024
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
The publisher hasn’t deposited this paper’s reference list.
Research works printed but not linked: 45
- Sotiris Anagnostidis, Dario Pavllo, Luca Biggio, Lorenzo Noci, Aurelien Lucchi, and Thomas Hof- mann. 2023. Dynamic context pruning for efficient and interpretable autoregressive transformers. In Thirty-seventh Conference on Neural Information Processing Systems.
- Martin Arjovsky, Amar Shah, and Yoshua Bengio. 2016. Unitary evolution recurrent neural networks. In In- ternational conference on machine learning, pages 1120-1128. PMLR.
- Maximilian Beck, Korbinian Pöppel, Markus Span- ring, Andreas Auer, Oleksandra Prudnikova, Michael Kopp, Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. 2024. xLSTM: Extended long short- term memory. arXiv:2405.04517. · arXiv
- Iz Beltagy, Matthew E. Peters, and Arman Cohan. 2020. Longformer: The long-document transformer. arXiv:2004.05150. · arXiv
- Steven Bird, Ewan Klein, and Edward Loper. 2009. Nat- ural language processing with Python: analyzing text with the natural language toolkit. O'Reilly Media, Inc.
- William Brandon, Mayank Mishra, Aniruddha Nrusimha, Rameswar Panda, and Jonathan Ragan Kelly. 2024. Reducing transformer key-value cache size with cross-layer attention. arXiv:2405.12981. · arXiv
- Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901.
- Shouyuan Chen, Sherman Wong, Liangjian Chen, and Yuandong Tian. 2023. Extending context window of large language models via positional interpolation. arXiv:2306.15595. · arXiv
- Jeffrey L. Elman. 1990. Finding structure in time. Cog- nitive Science, 14(2):179-211. · DOI · Paper page
- Suyu Ge, Yunan Zhang, Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao. 2024. Model tells you what to discard: Adaptive KV cache compression for LLMs. In ICLR 2024.
- Albert Gu and Tri Dao. 2023. Mamba: Linear- time sequence modeling with selective state spaces. arXiv:2312.00752. · arXiv
- Albert Gu, Karan Goel, and Christopher Ré. 2022. Ef- ficiently modeling long sequences with structured state spaces. In International Conference on Learn- ing Representations.
- Ankit Gupta, Albert Gu, and Jonathan Berant. 2022. Di- agonal state spaces are as effective as structured state spaces. Advances in Neural Information Processing Systems, 35:22982-22994.
- Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735- 1780.
- DeLesley Hutchins, Imanol Schlag, Yuhuai Wu, Ethan Dyer, and Behnam Neyshabur. 2022. Block-recurrent transformers. In Advances in Neural Information Processing Systems.
- Samy Jelassi, David Brandfonbrener, Sham M. Kakade, and Eran Malach. 2024. Repeat after me: Trans- formers are better than state space models at copying. arXiv:2402.01032. · arXiv
- Albert Q. Jiang, Alexandre Sablayrolles, Arthur Men- sch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Re- nard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timo- thée Lacroix, and William El Sayed. 2023. Mistral 7B. arXiv:2310.06825. · arXiv
- Hao Kang, Qingru Zhang, Souvik Kundu, Geonhwa Jeong, Zaoxing Liu, Tushar Krishna, and Tuo Zhao. 2024. GEAR: An efficient KV cache compression recipe for near-lossless generative inference of LLM. arXiv:2403.05527. · arXiv
- Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pap- pas, and François Fleuret. 2020. Transformers are rnns: Fast autoregressive transformers with linear attention. In International conference on machine learning, pages 5156-5165. PMLR.
- Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. 2024. SnapKV: LLM knows what you are looking for before genera- tion. arXiv:2404.14469. · arXiv
- Hanxiao Liu, Zihang Dai, David So, and Quoc V Le. 2021. Pay attention to MLPs. In Advances in Neural Information Processing Systems, volume 34, pages 9204-9215.
- Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasios Kyril- lidis, and Anshumali Shrivastava. 2024. Scis- sorhands: Exploiting the persistence of importance hypothesis for llm kv cache compression at test time. In Advances in Neural Information Processing Sys- tems, volume 36.
- Harsh Mehta, Ankit Gupta, Ashok Cutkosky, and Behnam Neyshabur. 2023. Long range language modeling via gated state spaces. In The Eleventh In- ternational Conference on Learning Representations.
- Stephen Merity. 2019. Single headed attention RNN: Stop thinking with your head. arXiv:1911.11423. · arXiv
- Paul Michel, Omer Levy, and Graham Neubig. 2019. Are sixteen heads really better than one? In Ad- vances in Neural Information Processing Systems, volume 32.
- Antonio Orvieto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. 2023. Resurrecting recurrent neural net- works for long sequences. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org.
- Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A. Smith, and Lingpeng Kong. 2021. Random feature attention. In Proc. of ICLR.
- Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Anselm Levskaya, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. 2023. Efficiently scaling transformer in- ference. In Proc. of MLSys.
- Ofir Press, Noah A. Smith, and Mike Lewis. 2022. Train short, test long: Attention with linear biases enables input length extrapolation. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net.
- Jack W. Rae, Anna Potapenko, Siddhant M. Jayaku- mar, Chloe Hillier, and Timothy P. Lillicrap. 2020. Compressive transformers for long-range sequence modelling. In International Conference on Learning Representations.
- Siyu Ren and Kenny Q. Zhu. 2024. On the efficacy of eviction policy for key-value constrained generative language model inference. arXiv:2402.06262. · arXiv
- David R. So, Wojciech Mańke, Hanxiao Liu, Zihang Dai, Noam Shazeer, and Quoc V. Le. 2024. Primer: searching for efficient transformers for language mod- eling. In Proceedings of the 35th International Con- ference on Neural Information Processing Systems, NeurIPS '21, Red Hook, NY, USA.
- Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei. 2023. Retentive network: A suc- cessor to transformer for large language models. arXiv:2307.08621. · arXiv
- Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023a. LLaMA: Open and efficient foundation language models. arXiv:2302.13971. · arXiv
- Hugo Touvron, Louis Martin, Kevin Stone, Peter Al- bert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, An- thony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Di- ana Liskovich, Yinghai Lu, Yuning Mao, Xavier Mar- tinet, Todor Mihaylov, Pushkar Mishra, Igor Moly- bog, Yixin Nie, Andrew Poulton, Jeremy Reizen- stein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subrama- nian, Xiaoqing Ellen Tan, Binh Tang, Ross Tay- lor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Ro- driguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. 2023b. LLaMA 2: Open foundation and fine-tuned chat models. arXiv:2307.09288. · arXiv
- Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in neural information processing systems, 30.
- Peiyi Wang, Lei Li, Liang Chen, Zefan Cai, Dawei Zhu, Binghuai Lin, Yunbo Cao, Lingpeng Kong, Qi Liu, Tianyu Liu, and Zhifang Sui. 2024. Large lan- guage models are not fair evaluators. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 9440-9450, Bangkok, Thailand. Association for Computational Linguistics.
- Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. 2020. Linformer: Self-attention with linear complexity. arXiv:2006.04768. · arXiv
- Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. 2024. Efficient streaming language models with attention sinks. In Proc. of ICLR.
- Dongjie Yang, Xiaodong Han, Yan Gao, Yao Hu, Shilin Zhang, and Hai Zhao. 2024. PyramidInfer: Pyramid KV cache compression for high-throughput LLM inference. In Findings of the Association for Com- putational Linguistics ACL 2024, pages 3258-3270, Bangkok, Thailand and virtual meeting. Association for Computational Linguistics.
- Songlin Yang, Bailin Wang, Yikang Shen, Rameswar Panda, and Yoon Kim. 2023. Gated linear atten- tion transformers with hardware-efficient training. arXiv:2312.06635. · arXiv
- Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago On- tanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. 2020. Big bird: Transformers for longer sequences. Advances in neural information processing systems, 33:17283-17297.
- Amir Zandieh, Insu Han, Vahab Mirrokni, and Amin Karbasi. 2024. SubGen: Token generation in sublin- ear time and memory. arXiv:2402.06082. · arXiv
- Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, Zhangyang "Atlas" Wang, and Beidi Chen. 2023. H2o: Heavy-hitter oracle for efficient generative in- ference of large language models. In Advances in Neural Information Processing Systems, volume 36, pages 34661-34710.
- Chunting Zhou, Pengfei Liu, Puxin Xu, Srinivasan Iyer, Jiao Sun, Yuning Mao, Xuezhe Ma, Avia Efrat, Ping Yu, LILI YU, Susan Zhang, Gargi Ghosh, Mike Lewis, Luke Zettlemoyer, and Omer Levy. 2023. Lima: Less is more for alignment. In Advances in Neural Information Processing Systems, volume 36, pages 55006-55021.
Cited by
Sorted by citations
State-space modeling in long sequence processing: a survey on recurrence in the transformer era
Tiezzi, M., Casoni, M., Betti, A., Gori, M., & Melacci, S. (2025) · Neural Networks · doi:10.1016/j.neunet.2025.108039 · Cited by 21 · see citing works
Goldstein, A., Ham, E., Schain, M., Nastase, S. A., Aubrey, B., Zada, Z., Grinstein-Dabush, A., Gazula, H., Feder, A., Doyle, W., et al. (2025) · Nature Communications · doi:10.1038/s41467-025-65518-0 · Cited by 43 · see citing works
Graph-aware isomorphic attention for adaptive dynamics in transformers
Buehler, M. J. (2025) · APL Machine Learning · doi:10.1063/5.0256873 · Cited by 17 · see citing works
Language conditioned multi-scale visual attention networks for visual grounding
Yao, H., Wang, L., Cai, C., Wang, W., Zhang, Z., & Shang, X. (2024) · Image and Vision Computing · doi:10.1016/j.imavis.2024.105242 · Cited by 6 · see citing works
FINCH: Prompt-guided Key-Value Cache Compression for Large Language Models
Corallo, G., & Papotti, P. (2024) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00716 · Cited by 5 · see citing works
WeightedKV: Attention Scores Weighted Key-Value Cache Merging for Large Language Models
Yuan, J., He, Z., Bai, H., Leng, J., & Jiang, B. (2025) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp49660.2025.10889583 · Cited by 4 · see citing works
Enhancing Large Language Model Inference Efficiency via Lookahead Cache Filtering
Ou, J., Chen, Y., Jiang, S., & Tian, W. (2025) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp49660.2025.10888646 · Cited by 3 · see citing works
Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores
Chari, V., & Van Durme, B. (2025) · arXiv · doi:10.48550/arxiv.2507.08143 · Cited by 1 · see citing works
“Performance of eviction methods on NIAH and QA tasks is shown in Figure 4, and demonstrates the variable performance that different tasks support.”
AQPIM: Breaking the PIM Capacity Wall for LLMs with in-Memory Activation Quantization
Matsushima, K., Okoshi, Y., Motomura, M., & Fujiki, D. (2026) · IEEE International Symposium on High-Performance Computer Architecture (HPCA) · doi:10.1109/hpca68181.2026.11408452 · Cited by 1 · see citing works
MKA: Memory-Keyed Attention for Efficient Long-Context Reasoning
Liu, D., Yu, Y., Lengerich, B. J., & Wu, Y. N. (2026) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/3801487.3801812 · Cited by 1 · see citing works
An, Y., Lu, C., Zhu, K., Yu, T., Zhao, C., Wu, H., Tang, M., & Wang, J. (2026) · arXiv · doi:10.48550/arxiv.2605.08840
“We compare ReST-KV with five baselines: (1) Fixed Attention Patterns: StreamingLLM (Xiao et al., 2023); (2) Eviction Indicator: H2O (Zhang et al., 2023), TOVA (Oren et al., 2024), SnapKV (Li et al., 2024b), LaCache (Shi et al., 2025).”
How Query Visibility Changes KV-Cache Compression Rankings: A Matched-Budget Audit
Luo, D., Liang, C., & Xuan, J. (2026) · arXiv · doi:10.48550/arxiv.2607.11942
IndexMem: Learned KV-Cache Eviction with Latent Memory for Long-Context LLM Inference
Yang, X., Gu, H., Xu, B., Li, L., Liu, B., Liu, J., Zhu, Q., Guo, Y., & Han, S. (2026) · arXiv · doi:10.48550/arxiv.2605.25475
“We can plug in other eviction rules (e.g., TOVA (Oren et al., 2024), KeyDiff, Expected Attention) by specifying their corresponding score function S = f ( · ) under this same framework.”
InfluentialLearning What to Remember: Test-Time Training via Context Distillation
Wang, Z., Dang, X., Zhu, R.-J., Wen, Z., Fu, H., Chai, W., & Lee, J. D. (2026) · arXiv · doi:10.48550/arxiv.2608.01672
“Existing context-compression methods often use distillation to produce an offline prompt, memory, or compressed KV representation before generation [7, 28, 53, 32, 19, 34, 56, 30, 31].”
Corm: Cache Optimization with Recent Message for Large Language Model InferencePreprint
Huang, Z., Jiang, H., & Dai, J. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5388897
Improving Representations for Language Modeling
Godey, N. (2024) · theses.fr (ABES) · doi:10.70675/b6a15d0ez15bez43e5za967z16a069e0a8bb
LineAR: Autoregressive Image Generation Needs Only a Few Lines of Cached Tokens
Qin, Z., Lv, Y., Lin, M., Zhang, Z., Gan, C., Chen, T., Shen, L., Hou, J., Lim, C. H., Wen, F., et al. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-37035-8_33
Key-value-free transformers: Training cacheless decoders via residual stream stabilisation
Qasim, K. U., Zhang, J., Shaheen, M. K., & Alharith, R. (2026) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2026.116397
Myopia Rectification: KV Cache Pruning for MLLMs via Dynamic Attention Subsidy and Token Reclamation
Zhuang, J., Lu, L., Dai, M., Chen, J., Liu, Q., & Hu, H. (2026) · doi:10.1109/cvprf71909.2026.00866
Efficient Long-Context Modeling in Diffusion Language Models via Block Approximate Sparse Attention
Zhang, W., Wu, Y., Wang, H., Liu, Y., Dou, H., Yang, S., Wu, S., Zhao, H., & Jia, J. (2026) · doi:10.1109/cvprf71909.2026.00278
PrismKV: Harmonizing Heterogeneous Compression Strategies through Layer-adaptive Partition Scoring
侍冬成, Cao, Y., & Jiang, H. (2026) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn69854.2026.11729267
Cartridges: Lightweight and general-purpose long context representations via self-study
Eyuboglu, S., Ehrlich, R., Arora, S., Guha, N., Zinsley, D., Liu, E., Tennien, W., Rudra, A., Zou, J., Mirhoseini, A., et al. (2025) · arXiv · doi:10.48550/arxiv.2506.06266
- Authors
- Oren, M., Hassid, M., Yarden, N., Adi, Y., & Schwartz, R.
- Affiliations
- Hebrew University of Jerusalem (IL)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2024
- Pages
- 18724-18741
- arXiv
- 2401.06104
- OpenAlex
- W4404782921
- Cited by
- 16
- References
- 0
- Citations by year
- 2026: 7 · 2025: 6 · 2024: 3
- FWCI
- 4.62
- Type
- conference paper
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- Conference on Empirical Methods in Natural Language Processing (EMNLP) (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion, cc-by-sa)
- arXiv (Cornell University)
- Funders
- National Science Foundation (2020793)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Neural Network Applications
- Keywords
- transformer models, key-value cache compression, training-free compression, long-range dependencies, large language models, decoder-only transformer, inference throughput
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
