{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T04:40:07Z","timestamp":1747888807652,"version":"3.41.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T00:00:00Z","timestamp":1745452800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T00:00:00Z","timestamp":1745452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Institute for Advanced Studies of the University of Luxembourg","award":["AUDACITY-IDAE-2021"],"award-info":[{"award-number":["AUDACITY-IDAE-2021"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Transformers have achieved state-of-the-art performance in most common tasks to which they have been applied. Those achievements are attributed to the Self-Attention mechanism at their core. Self-Attention is understood to map the relationship between tokens of any given sequence. This exhaustive mapping incurs massive costs in memory and inference time, as Self-Attention scales quadratically with regard to sequence length. Standard Self-Attention has required increasingly large compute and memory usage when applied to long input sequences because of this memory and time bottleneck. Efficient Transformers emerged as performant alternatives demonstrating good scalability and occasionally better tracking of long-range dependencies. Their efficiency gains are obtained through different methods, usually focusing on the linear scaling of the attention matrix through sparsification, approximation, or other methods. Among existing approaches, those using low-rank approximation present particular advantages because of their compatibility with standard Self-Attention-based models, allowing for weight transfers and other time-saving schemes. More recently, hardware-aware versions of Self-Attention (e.g., FlashAttention) have mitigated all memory bottlenecks and have alleviated its compute burden. Unfortunately, hardware-aware Self-Attentions have stricter hardware compatibility requirements making Efficient Transformers still relevant for use on older or less powerful hardware. Furthermore, some Efficient Transformers can even be applied in an hardware-aware manner to further improve training and inference speed. In this paper, we propose a novel linear approximation method for Self-Attention inspired by the CUR approximation method. This method, proposed in two versions (one leveraging FlashAttention), is conceived as a drop-in replacement for standard Self-Attention with weights compatibility. Our method compares favorably to standard Transformers\u2019 and Efficient Transformers\u2019 performances on varied tasks and demonstrates a significant decrease in memory footprint as well as competitive performance in training speed, even compared to similar methods.<\/jats:p>","DOI":"10.1007\/s10994-025-06768-3","type":"journal-article","created":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T21:22:53Z","timestamp":1745529773000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Drop-in efficient self-attention approximation method"],"prefix":"10.1007","volume":"114","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-4228-9494","authenticated-orcid":false,"given":"Damien","family":"Fran\u00e7ois","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3107-3128","authenticated-orcid":false,"given":"Mathis","family":"Saillot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4052-475X","authenticated-orcid":false,"given":"Jacques","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7270-9869","authenticated-orcid":false,"given":"Tegawend\u00e9 F.","family":"Bissyand\u00e9","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8955-8304","authenticated-orcid":false,"given":"Alexander","family":"Skupin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,24]]},"reference":[{"key":"6768_CR1","unstructured":"Beltagy, I., Peters, M.E., & Cohan, A. (2020). Longformer: The long-document transformer. arXiv preprint arXiv:2004.05150"},{"key":"6768_CR2","unstructured":"Child, R., Gray, S., Radford, A., & Sutskever, I. (2019). Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509"},{"key":"6768_CR3","unstructured":"Choromanski, K., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J., Mohiuddin, A., & Kaiser, L., et al. (2020). Rethinking attention with performers. arXiv preprint arXiv:2009.14794"},{"key":"6768_CR4","doi-asserted-by":"crossref","unstructured":"Dai, Z., Yang, Z., Yang, Y., Carbonell, J.G., Le, Q.V., & Salakhutdinov, R. (2019). Transformer-xl: Attentive language models beyond a fixed-length context. In: Annual Meeting of the Association for Computational Linguistics. https:\/\/api.semanticscholar.org\/CorpusID:57759363","DOI":"10.18653\/v1\/P19-1285"},{"key":"6768_CR5","unstructured":"Dao, T. (2023). FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning. ArXiv abs\/2307.08691"},{"key":"6768_CR6","unstructured":"Dao, T., Fu, D.Y., Ermon, S., Rudra, A., & R\u2019e, C. (2022). Flashattention: Fast and memory-efficient exact attention with io-awareness. ArXiv abs\/2205.14135"},{"key":"6768_CR7","unstructured":"Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., & Houlsby, N. (2020). An image is worth 16x16 words: Transformers for image recognition at scale., ArXiv abs\/2010.11929"},{"key":"6768_CR8","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1137\/07070471X","volume":"30","author":"P Drineas","year":"2007","unstructured":"Drineas, P., Mahoney, M. W., & Muthukrishnan, S. (2007). Relative-error cur matrix decompositions. SIAM Journal on Matrix Analysis and Applications, 30, 844\u2013881.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"6768_CR9","unstructured":"Ho, J., Kalchbrenner, N., Weissenborn, D., & Salimans, T. (2019). Axial attention in multidimensional transformers. arXiv preprint arXiv:1912.12180"},{"key":"6768_CR10","unstructured":"Hu, E.J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., & Chen, W. (2021). LoRA: Low-Rank Adaptation of Large Language Models. https:\/\/arxiv.org\/abs\/2106.09685"},{"key":"6768_CR11","unstructured":"Katharopoulos, A., Vyas, A., Pappas, N., & Fleuret, F. (2020). Transformers are rnns: Fast autoregressive transformers with linear attention. In: International Conference on Machine Learning, pp. 5156\u20135165. PMLR"},{"key":"6768_CR12","unstructured":"Kitaev, N., Kaiser, L., & Levskaya, A. (2020). Reformer: The efficient transformer. ArXiv abs\/2001.04451"},{"key":"6768_CR13","unstructured":"Krizhevsky, A. (2009). Learning multiple layers of features from tiny images."},{"key":"6768_CR14","doi-asserted-by":"crossref","unstructured":"Linsley, D.A., Kim, J., Veerabadran, V., & Serre, T. (2018). Learning long-range spatial dependencies with horizontal gated-recurrent units. ArXiv abs\/1805.08315","DOI":"10.32470\/CCN.2018.1116-0"},{"key":"6768_CR15","unstructured":"Ma, X., Kong, X., Wang, S., Zhou, C., May, J., Ma, H., & Zettlemoyer, L. (2021). Luna: Linear unified nested attention. ArXiv abs\/2106.01540"},{"key":"6768_CR16","unstructured":"Ma, X., Zhou, C., Kong, X., He, J., Gui, L., Neubig, G., May, J., & Zettlemoyer, L. (2022). Mega: Moving average equipped gated attention. ArXiv abs\/2209.10655"},{"key":"6768_CR17","unstructured":"Maas, A.L., Daly, R.E., Pham, P.T., Huang, D., Ng, A., & Potts, C. (2011). Learning word vectors for sentiment analysis. In: Annual Meeting of the Association for Computational Linguistics"},{"key":"6768_CR18","doi-asserted-by":"crossref","unstructured":"Nangia, N., & Bowman, S.R. (2018). Listops: A diagnostic dataset for latent tree learning. ArXiv abs\/1804.06028","DOI":"10.18653\/v1\/N18-4013"},{"key":"6768_CR19","unstructured":"Parmar, N., Vaswani, A., Uszkoreit, J., Kaiser, L., Shazeer, N., Ku, A., & Tran, D. (2018). Image transformer. In: International Conference on Machine Learning, pp. 4055\u20134064. PMLR"},{"key":"6768_CR20","unstructured":"Peng, H., Pappas, N., Yogatama, D., Schwartz, R., Smith, N.A., & Kong, L. (2021). Random feature attention. arXiv preprint arXiv:2103.02143"},{"key":"6768_CR21","unstructured":"Peng, B., Quesnelle, J., Fan, H., & Shippole, E. (2023). YaRN: Efficient Context Window Extension of Large Language Models. https:\/\/arxiv.org\/abs\/2309.00071"},{"key":"6768_CR22","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1017\/S0305004100030401","volume":"51","author":"R Penrose","year":"1955","unstructured":"Penrose, R. (1955). A generalized inverse for matrices. Mathematical Proceedings of the Cambridge Philosophical Society, 51, 406\u2013413.","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"key":"6768_CR23","unstructured":"Qin, B., Li, J., Tang, S., & Zhuang, Y. (2022). Dba: Efficient transformer with dynamic bilinear low-rank attention. ArXiv abs\/2211.16368"},{"key":"6768_CR24","doi-asserted-by":"crossref","unstructured":"Qiu, J., Ma, H., Levy, O., Yih, S., Wang, S., & Tang, J. (2019). Blockwise self-attention for long document understanding. ArXiv abs\/1911.02972","DOI":"10.18653\/v1\/2020.findings-emnlp.232"},{"key":"6768_CR25","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1007\/s10579-012-9211-2","volume":"47","author":"DR Radev","year":"2009","unstructured":"Radev, D. R., Muthukrishnan, P., Qazvinian, V., & Abu-Jbara, A. (2009). The acl anthology network corpus. Language Resources and Evaluation, 47, 919\u2013944.","journal-title":"Language Resources and Evaluation"},{"key":"6768_CR26","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1162\/tacl_a_00353","volume":"9","author":"A Roy","year":"2021","unstructured":"Roy, A., Saffar, M., Vaswani, A., & Grangier, D. (2021). Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 9, 53\u201368.","journal-title":"Transactions of the Association for Computational Linguistics"},{"issue":"3","key":"6768_CR27","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s11263-015-0816-y","volume":"115","author":"O Russakovsky","year":"2015","unstructured":"Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., Berg, A. C., & Fei-Fei, L. (2015). ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3), 211\u2013252. https:\/\/doi.org\/10.1007\/s11263-015-0816-y","journal-title":"International Journal of Computer Vision (IJCV)"},{"key":"6768_CR28","unstructured":"Tay, Y., Dehghani, M., Abnar, S., Shen, Y., Bahri, D., Pham, P., Rao, J., Yang, L., Ruder, S., & Metzler, D. (2020). Long range arena: A benchmark for efficient transformers. ArXiv abs\/2011.04006"},{"key":"6768_CR29","doi-asserted-by":"crossref","unstructured":"Tillet, P., Kung, H.-T., & Cox, D.D. (2019). Triton: an intermediate language and compiler for tiled neural network computations. Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages","DOI":"10.1145\/3315508.3329973"},{"key":"6768_CR30","unstructured":"Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, \u0141, & Polosukhin, I. (2017). Attention is all you need. Advances in neural information processing systems,30."},{"key":"6768_CR31","unstructured":"Wang, S., Li, B.Z., Khabsa, M., Fang, H., & Ma, H. (2020). Linformer: Self-attention with linear complexity. ArXiv abs\/2006.04768"},{"key":"6768_CR32","doi-asserted-by":"publisher","unstructured":"Wu, Y., Kan, S., Zeng, M., & Li, M. (2023). Singularformer: Learning to decompose self-attention to linearize the complexity of transformer. In: Elkind, E. (ed.) Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, pp. 4433\u20134441. International Joint Conferences on Artificial Intelligence Organization. https:\/\/doi.org\/10.24963\/ijcai.2023\/493 . Main Track.","DOI":"10.24963\/ijcai.2023\/493"},{"key":"6768_CR33","doi-asserted-by":"crossref","unstructured":"Xiong, Y., Zeng, Z., Chakraborty, R., Tan, M., Fung, G. M., Li, Y., & Singh, V. (2021). Nystr\u00f6mformer: A nystr\u00f6m-based algorithm for approximating self-attention. Proceedings of the ... AAAI Conference on Artificial Intelligence. AAAI Conference on Artificial Intelligence,35(16), 14138\u201314148.","DOI":"10.1609\/aaai.v35i16.17664"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-025-06768-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-025-06768-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-025-06768-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T04:02:39Z","timestamp":1747886559000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-025-06768-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,24]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["6768"],"URL":"https:\/\/doi.org\/10.1007\/s10994-025-06768-3","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2025,4,24]]},"assertion":[{"value":"8 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"139"}}