{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,5]],"date-time":"2026-08-05T18:22:43Z","timestamp":1785954163991,"version":"3.56.0"},"reference-count":55,"publisher":"MIT Press - Journals","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Transactions of the Association for Computational Linguistics"],"published-print":{"date-parts":[[2021,2]]},"abstract":"<jats:p>Self-attention has recently been adopted for a wide range of sequence modeling problems. Despite its effectiveness, self-attention suffers from quadratic computation and memory requirements with respect to sequence length. Successful approaches to reduce this complexity focused on attending to local sliding windows or a small set of locations independent of content. Our work proposes to learn dynamic sparse attention patterns that avoid allocating computation and memory to attend to content unrelated to the query of interest. This work builds upon two lines of research: It combines the modeling flexibility of prior work on content-based sparse attention with the efficiency gains from approaches based on local, temporal sparse attention. Our model, the Routing Transformer, endows self-attention with a sparse routing module based on online k-means while reducing the overall complexity of attention to O( n<jats:sup>1.5<\/jats:sup>d) from O( n<jats:sup>2<\/jats:sup>d) for sequence length n and hidden dimension d. We show that our model outperforms comparable sparse attention models on language modeling on Wikitext-103 (15.8 vs 18.3 perplexity), as well as on image generation on ImageNet-64 (3.43 vs 3.44 bits\/dim) while using fewer self-attention layers. Additionally, we set a new state-of-the-art on the newly released PG-19 data-set, obtaining a test perplexity of 33.2 with a 22 layer Routing Transformer model trained on sequences of length 8192. We open-source the code for Routing Transformer in Tensorflow.<jats:sup>1<\/jats:sup><\/jats:p>","DOI":"10.1162\/tacl_a_00353","type":"journal-article","created":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T21:23:29Z","timestamp":1613683409000},"page":"53-68","source":"Crossref","is-referenced-by-count":329,"title":["Efficient Content-Based Sparse Attention with Routing Transformers"],"prefix":"10.1162","volume":"9","author":[{"given":"Aurko","family":"Roy","sequence":"first","affiliation":[{"name":"Google Research."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad","family":"Saffar","sequence":"additional","affiliation":[{"name":"Google Research."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ashish","family":"Vaswani","sequence":"additional","affiliation":[{"name":"Google Research."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Grangier","sequence":"additional","affiliation":[{"name":"Google Research."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"281","reference":[{"key":"bib1","first-page":"3159","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"33","author":"Al-Rfou Rami","year":"2019"},{"key":"bib2","author":"Auvolat Alex","year":"2015","journal-title":"arXiv preprint arXiv:1507.05910"},{"key":"bib3","author":"Ba Jimmy Lei","year":"2016","journal-title":"arXiv preprint arXiv:1607.06450"},{"key":"bib4","volume-title":"International Conference on Learning Representations","author":"Baevski Alexei","year":"2019"},{"key":"bib5","volume-title":"3rd International Conference on Learning Representations, ICLR 2015","author":"Bahdanau Dzmitry","year":"2015"},{"issue":"3","key":"bib6","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1109\/TNN.2004.824416","volume":"15","author":"Banerjee Arindam","year":"2004","journal-title":"IEEE Transactions on Neural Networks"},{"key":"bib7","author":"Bengio Yoshua","year":"2013","journal-title":"arXiv preprint arXiv: 1308.3432"},{"key":"bib8","first-page":"606","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16\u201318 April 2019, Naha, Okinawa, Japan","author":"Blondel Mathieu","year":"2019"},{"key":"bib9","first-page":"585","volume-title":"Advances in Neural Information Processing Systems","author":"Bottou Leon","year":"1995"},{"key":"bib10","first-page":"864","volume-title":"International Conference on Machine Learning","author":"Xi Chen","year":"2018"},{"key":"bib11","author":"Child Rewon","year":"2019","journal-title":"arXiv preprint arXiv:1904.10509"},{"key":"bib12","volume-title":"6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 \u2013 May 3, 2018, Conference Track Proceedings","author":"Chiu Chung-Cheng","year":"2018"},{"key":"bib13","author":"Cho Kyunghyun","year":"2014","journal-title":"arXiv preprint arXiv:1406.7362"},{"key":"bib14","first-page":"1724","volume-title":"Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)","author":"Cho Kyunghyun","year":"2014"},{"key":"bib15","first-page":"577","volume-title":"Advances in Neural Information Processing Systems","author":"Chorowski Jan K.","year":"2015"},{"key":"bib16","doi-asserted-by":"crossref","first-page":"2174","DOI":"10.18653\/v1\/D19-1223","volume-title":"Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)","author":"Correia Gon\u00e7alo M.","year":"2019"},{"key":"bib17","first-page":"2978","volume-title":"Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics","author":"Dai Zihang","year":"2019"},{"key":"bib18","author":"Denoyer Ludovic","year":"2014","journal-title":"arXiv preprint arXiv:1410.0510"},{"key":"bib19","volume-title":"NAACL-HLT (1)","author":"Devlin Jacob","year":"2019"},{"key":"bib20","author":"Eigen David","year":"2013","journal-title":"arXiv preprint arXiv:1312.4314"},{"key":"bib21","author":"Gale Trevor","year":"2020","journal-title":"arXiv preprint arXiv:2006.10901"},{"key":"bib22","volume-title":"5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings","author":"Grave Edouard","year":"2017"},{"key":"bib23","author":"Graves Alex","year":"2014","journal-title":"arXiv preprint arXiv:1410.5401"},{"key":"bib24","first-page":"1462","volume-title":"Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6\u201311 July 2015","volume":"37","author":"Gregor Karol","year":"2015"},{"key":"bib25","volume-title":"International Conference on Learning Representations","author":"Holtzman Ari","year":"2020"},{"key":"bib26","volume-title":"International Conference on Learning Representations","author":"Huang Cheng-Zhi Anna","year":"2018"},{"key":"bib27","first-page":"3037","volume-title":"Proceedings of the 57th Conference of the Association for Computational Linguistics","author":"Indurthi Sathish Reddy","year":"2019"},{"key":"bib28","first-page":"5067","volume-title":"Advances in Neural Information Processing Systems","author":"Jaitly Navdeep","year":"2016"},{"key":"bib29","volume-title":"3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7\u20139, 2015, Conference Track Proceedings","author":"Kingma Diederik P.","year":"2015"},{"key":"bib30","first-page":"10215","volume-title":"Advances in Neural Information Processing Systems","author":"Kingma Durk P.","year":"2018"},{"key":"bib31","volume-title":"International Conference on Learning Representations","author":"Kitaev Nikita","year":"2020"},{"key":"bib32","first-page":"8548","volume-title":"Advances in Neural Information Processing Systems","author":"Lample Guillaume","year":"2019"},{"key":"bib33","volume-title":"International Conference on Learning Representations","author":"Liu Peter J.","year":"2018"},{"key":"bib34","first-page":"4487","volume-title":"Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics","author":"Liu Xiaodong","year":"2019"},{"key":"bib35","doi-asserted-by":"crossref","first-page":"1412","DOI":"10.18653\/v1\/D15-1166","volume-title":"Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing","author":"Luong Minh-Thang","year":"2015"},{"key":"bib36","unstructured":"Matt Mahoney. 2011. Large text compression benchmark.URL:\u00a0http:\/\/www.mattmahoney.net\/text\/text.html"},{"key":"bib37","doi-asserted-by":"crossref","first-page":"370","DOI":"10.18653\/v1\/P18-2059","volume-title":"Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)","author":"Malaviya Chaitanya","year":"2018"},{"key":"bib38","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/978-3-662-44415-3_4","volume-title":"Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR)","author":"Malinen Mikko I.","year":"2014"},{"key":"bib39","first-page":"349","volume-title":"Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing","author":"Martins Andr\u00e9 F. T.","year":"2017"},{"key":"bib40","volume-title":"International Conference on Learning Representations","author":"Menick Jacob","year":"2018"},{"key":"bib41","author":"Merity Stephen","year":"2018","journal-title":"arXiv preprint arXiv:1803.08240"},{"key":"bib42","volume-title":"5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24\u201326, 2017, Conference Track Proceedings","author":"Merity Stephen","year":"2017"},{"key":"bib43","first-page":"4055","volume-title":"International Conference on Machine Learning","author":"Parmar Niki","year":"2018"},{"key":"bib44","unstructured":"Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. 2018. Improving language understanding by generative pre-training.URL:\u00a0https:\/\/s3-us-west-2.amazonaws.com\/openai-assets\/research-covers\/languageunsupervised\/languageunderstandingpaper.pdf"},{"key":"bib45","first-page":"3621","volume-title":"Advances in Neural Information Processing Systems","author":"Rae Jack","year":"2016"},{"key":"bib46","first-page":"7524","volume-title":"Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics","author":"Rae Jack","year":"2020"},{"key":"bib47","volume-title":"International Conference on Learning Representations","author":"Rae Jack W.","year":"2020"},{"key":"bib48","first-page":"464","volume-title":"Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)","author":"Shaw Peter","year":"2018"},{"key":"bib49","volume-title":"5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24\u201326, 2017, Conference Track Proceedings","author":"Shazeer Noam","year":"2017"},{"key":"bib50","first-page":"4596","volume-title":"International Conference on Machine Learning","author":"Shazeer Noam","year":"2018"},{"key":"bib51","doi-asserted-by":"crossref","first-page":"331","DOI":"10.18653\/v1\/P19-1032","volume-title":"Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics","author":"Sukhbaatar Sainbayar","year":"2019"},{"key":"bib52","first-page":"4790","volume-title":"Advances in Neural Information Processing Systems","author":"Oord Aaron Van den","year":"2016"},{"key":"bib53","first-page":"5998","volume-title":"Advances in Neural Information Processing Systems","author":"Vaswani Ashish","year":"2017"},{"key":"bib54","first-page":"2048","volume-title":"Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6\u201311 July 2015","volume":"37","author":"Kelvin Xu","year":"2015"},{"key":"bib55","first-page":"5753","volume-title":"Advances in Neural Information Processing Systems","author":"Yang Zhilin","year":"2019"}],"container-title":["Transactions of the Association for Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/tacl_a_00353","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,25]],"date-time":"2021-04-25T09:02:55Z","timestamp":1619341375000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/tacl\/article\/97776"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2]]},"references-count":55,"alternative-id":["10.1162\/tacl_a_00353"],"URL":"https:\/\/doi.org\/10.1162\/tacl_a_00353","relation":{},"ISSN":["2307-387X"],"issn-type":[{"value":"2307-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2]]}}}