{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T01:37:13Z","timestamp":1772933833902,"version":"3.50.1"},"reference-count":108,"publisher":"IEEE","license":[{"start":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T00:00:00Z","timestamp":1765152000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T00:00:00Z","timestamp":1765152000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,12,8]]},"DOI":"10.1109\/bigdata66926.2025.11400978","type":"proceedings-article","created":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T20:57:57Z","timestamp":1772830677000},"page":"16-25","source":"Crossref","is-referenced-by-count":0,"title":["Why Softmax Attention Outperforms Linear Attention"],"prefix":"10.1109","author":[{"given":"Yichuan","family":"Deng","sequence":"first","affiliation":[{"name":"University of Washington,Seattle,WA"}]},{"given":"Zhao","family":"Song","sequence":"additional","affiliation":[{"name":"University of California, Berkeley,Berkeley,CA"}]},{"given":"Kaijun","family":"Yuan","sequence":"additional","affiliation":[{"name":"University of Bologna,Bologna,Italy"}]},{"given":"Tianyi","family":"Zhou","sequence":"additional","affiliation":[{"name":"University of Southern California,Los Angeles,CA"}]}],"member":"263","reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.1706.03762"},{"key":"ref2","article-title":"Bert: Pre-training of deep bidirectional transformers for language understanding","author":"Devlin","year":"2018","journal-title":"arXiv preprint"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.1907.11692"},{"key":"ref4","article-title":"Xlnet: Generalized autoregressive pretraining for language understanding","volume":"32","author":"Yang","year":"2019","journal-title":"Advances in neural information processing systems"},{"key":"ref5","first-page":"1877","article-title":"Language models are few-shot learners","volume":"33","author":"Brown","year":"2020","journal-title":"Advances in neural information processing systems"},{"key":"ref6","article-title":"Opt: Open pre-trained transformer language models","author":"Zhang","year":"2022","journal-title":"arXiv preprint"},{"key":"ref7","article-title":"Palm: Scaling language modeling with pathways","author":"Chowdhery","year":"2022","journal-title":"arXiv preprint"},{"key":"ref8","article-title":"Llama: Open and efficient foundation language models","author":"Touvron","year":"2023","journal-title":"arXiv preprint"},{"key":"ref9","article-title":"Llama 2: Open foundation and finetuned chat models","author":"Touvron","year":"2023","journal-title":"arXiv preprint"},{"key":"ref10","volume-title":"Adobe firefly","year":"2023"},{"key":"ref11","article-title":"An overview of bard: an early experiment with generative ai","volume-title":"Tech. rep., Technical report, Google AI, Tech. Rep.","author":"Manyika","year":"2023"},{"key":"ref12","article-title":"Lamda: Language models for dialog applications","author":"Thoppilan","year":"2022","journal-title":"arXiv preprint"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1145\/3490099.3511105"},{"key":"ref14","article-title":"Emergent abilities of large language models","author":"Wei","year":"2022","journal-title":"arXiv preprint"},{"key":"ref15","article-title":"Linear attention mechanism: An efficient attention for semantic segmentation","author":"Li","year":"2020","journal-title":"arXiv preprint"},{"key":"ref16","first-page":"5156","article-title":"Transformers are rnns: Fast autoregressive transformers with linear attention","volume-title":"International conference on machine learning. PMLR","author":"Katharopoulos","year":"2020"},{"key":"ref17","first-page":"3531","article-title":"Efficient attention: Attention with linear complexities","volume-title":"Proceedings of the IEEE\/CVF winter conference on applications of computer vision","author":"Shen","year":"2021"},{"key":"ref18","first-page":"27011","article-title":"Linear complexity randomized self-attention mechanism","volume-title":"International Conference on Machine Learning. PMLR","author":"Zheng","year":"2022"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1145\/3539618.3591717"},{"key":"ref20","article-title":"On the finegrained complexity of empirical risk minimization: Kernel methods and neural networks","volume":"30","author":"Backurs","year":"2017","journal-title":"Advances in Neural Information Processing Systems (NeurIPS)"},{"key":"ref21","article-title":"On the hardness of approximate and exact (bichromatic) maximum inner product","author":"Chen","year":"2018","journal-title":"CCC"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00077"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00057"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.52202\/075280-2755"},{"key":"ref25","article-title":"How to capture higher-order correlations? generalizing matrix softmax attention to kronecker computation","author":"Alman","year":"2023","journal-title":"arXiv preprint"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.52202\/075280-2087"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585157"},{"key":"ref28","article-title":"Fast rope attention: Combining the polynomial method and fast fourier transform","author":"Alman","year":"2025","journal-title":"arXiv preprint"},{"key":"ref29","doi-asserted-by":"crossref","DOI":"10.52202\/079017-1963","article-title":"The fine-grained complexity of gradient computation for training large language models","volume-title":"The Thirty-eighth Annual Conference on Neural Information Processing Systems","author":"Alman","year":"2024"},{"key":"ref30","article-title":"Only large weights (and not skip connections) can prevent the perils of rank collapse","author":"Alman","year":"2025","journal-title":"arXiv preprint"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/D16-1244"},{"key":"ref32","article-title":"A structured self-attentive sentence embedding","author":"Lin","year":"2017","journal-title":"arXiv preprint"},{"key":"ref33","first-page":"4593","article-title":"BERT rediscovers the classical NLP pipeline","volume-title":"Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics.","author":"Tenney"},{"key":"ref34","first-page":"63","article-title":"Analyzing the structure of attention in a transformer language model","volume-title":"Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP.","author":"Vig"},{"key":"ref35","first-page":"2733","article-title":"Designing and interpreting probes with control tasks","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":"Hewitt"},{"issue":"1","key":"ref36","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1162\/coli_a_00422","article-title":"Probing classifiers: Promises, short-comings, and advances","volume":"48","author":"Belinkov","year":"2022","journal-title":"Computational Linguistics"},{"key":"ref37","article-title":"On the turing completeness of modern neural network architectures","author":"P\u00e9rez","year":"2019","journal-title":"arXiv preprint"},{"key":"ref38","first-page":"455","article-title":"On the computational power of transformers and its implications in sequence modeling","volume-title":"Proceedings of the 24th Conference on Computational Natural Language Learning. Online: Association for Computational Linguistics","author":"Bhattamishra"},{"key":"ref39","article-title":"Are transformers universal approximators of sequence-to-sequence functions?","volume-title":"International Conference on Learning Representations","author":"Yun","year":"2020"},{"key":"ref40","first-page":"17413","article-title":"Scatterbrain: Unifying sparse and low-rank attention","volume":"34","author":"Chen","year":"2021","journal-title":"Advances in Neural Information Processing Systems (NeurIPS)"},{"key":"ref41","first-page":"7096","article-title":"On the Ability and Limitations of Transformers to Recognize Formal Languages","volume-title":"Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). Online: Association for Computational Linguistics","author":"Bhattamishra"},{"key":"ref42","doi-asserted-by":"crossref","first-page":"4301","DOI":"10.18653\/v1\/2020.findings-emnlp.384","article-title":"How can self-attention networks recognize Dyck-n languages?","author":"Ebrahimi","year":"2020","journal-title":"Findings of the Association for Computational Linguistics: EMNLP 2020. Online: Association for Computational Linguistics"},{"key":"ref43","first-page":"3770","article-title":"Self-attention networks can process bounded hierarchical languages","volume-title":"Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). Online: Association for Computational Linguistics","author":"Yao"},{"key":"ref44","volume-title":"Unveiling transformers with lego: a synthetic reasoning task","author":"Zhang","year":"2022"},{"key":"ref45","article-title":"Pixelated butterfly: Simple and efficient sparse training for neural network models","author":"Dao","year":"2022","journal-title":"ICLR"},{"key":"ref46","article-title":"Rethinking attention with performers","author":"Choromanski","year":"2020","journal-title":"arXiv preprint"},{"key":"ref47","article-title":"Deja vu: Contextual sparsity for efficient llms at inference time","author":"Liu","year":"2023","journal-title":"ICML"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i16.17664"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-78172-8_1"},{"key":"ref50","article-title":"Generating long sequences with sparse transformers","author":"Child","year":"2019","journal-title":"arXiv preprint"},{"key":"ref51","article-title":"Reformer: The efficient transformer","author":"Kitaev","year":"2020","journal-title":"arXiv preprint"},{"key":"ref52","article-title":"Linformer: Self-attention with linear complexity","author":"Wang","year":"2020","journal-title":"arXiv preprint"},{"key":"ref53","first-page":"6476","article-title":"Smyrf-efficient attention using asymmetric clustering","volume":"33","author":"Daras","year":"2020","journal-title":"Advances in Neural Information Processing Systems (NeurIPS)"},{"key":"ref54","article-title":"Pixelated butterfly: Simple and efficient sparse training for neural network models","volume-title":"International Conference on Learning Representations (ICLR)","author":"Chen","year":"2022"},{"key":"ref55","article-title":"Kdeformer: Accelerating transformers via kernel density estimation","author":"Zandieh","year":"2023","journal-title":"ICML"},{"key":"ref56","article-title":"Algorithm and hardness for dynamic attention maintenance in large language models","author":"Brand","year":"2023","journal-title":"arXiv preprint"},{"key":"ref57","article-title":"Randomized and deterministic attention sparsification algorithms for over-parameterized feature dimension","author":"Deng","year":"2023","journal-title":"arxiv preprint"},{"key":"ref58","article-title":"Polysketchformer: Fast transformers via sketches for polynomial kernels","author":"Kacham","year":"2023","journal-title":"arXiv preprint"},{"key":"ref59","article-title":"Hyperattention: Longcontext attention in near-linear time","author":"Han","year":"2023","journal-title":"arXiv preprint"},{"key":"ref60","article-title":"Improving lengthgeneralization in transformers via task hinting","author":"Awasthi","year":"2023","journal-title":"arXiv preprint"},{"key":"ref61","article-title":"A very preliminary analysis of dall-e 2","author":"Marcus","year":"2022","journal-title":"arXiv preprint"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.29007\/lcs5"},{"key":"ref63","article-title":"A mathematical theory of attention","author":"Vuckovic","year":"2020","journal-title":"arXiv preprint"},{"key":"ref64","first-page":"15 383","article-title":"Why are adaptive methods good for attention models?","volume":"33","author":"Zhang","year":"2020","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref65","article-title":"Inductive biases and variable creation in self-attention mechanisms","author":"Edelman","year":"2021","journal-title":"arXiv preprint"},{"key":"ref66","article-title":"Approximating how single head attention learns","author":"Snell","year":"2021","journal-title":"arXiv preprint"},{"key":"ref67","article-title":"Statistically meaningful approximation: a case study on approximating turing machines with transformers","author":"Wei","year":"2021","journal-title":"arXiv preprint"},{"key":"ref68","article-title":"cosformer: Rethinking softmax in attention","author":"Qin","year":"2022","journal-title":"arXiv preprint"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/2022.emnlp-main.473"},{"key":"ref70","article-title":"Convergence of twolayer regression with nonlinear units","author":"Deng","year":"2023","journal-title":"arXiv preprint"},{"key":"ref71","article-title":"Zeroth order algorithm for softmax attention optimization","author":"Deng","year":"2023","journal-title":"arXiv preprint"},{"key":"ref72","article-title":"Linear lognormal attention with unbiased concentration","author":"Nahshan","year":"2023","journal-title":"arXiv preprint"},{"key":"ref73","article-title":"Universal approximation with softmax attention","author":"Hu","year":"2025","journal-title":"arXiv preprint"},{"key":"ref74","article-title":"Attention mechanism, max-affine partition, and universal approximation","author":"Liu","year":"2025","journal-title":"arXiv preprint"},{"key":"ref75","article-title":"Minimalist softmax attention provably learns constrained boolean functions","author":"Hu","year":"2025","journal-title":"arXiv preprint"},{"key":"ref76","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/2023.emnlp-main.1029"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1109\/BigData59044.2023.10386872"},{"key":"ref78","article-title":"An over-parameterized exponential regression","author":"Gao","year":"2023","journal-title":"arXiv preprint"},{"key":"ref79","article-title":"Solving regularized exp, cosh and sinh regression problems","author":"Li","year":"2023","journal-title":"arXiv preprint"},{"key":"ref80","article-title":"Attention scheme inspired softmax regression","author":"Deng","year":"2023","journal-title":"arXiv preprint"},{"key":"ref81","article-title":"In-context learning for attention scheme: from single softmax regression to multiple softmax regression via a tensor trick","author":"Gao","year":"2023","journal-title":"arXiv preprint"},{"key":"ref82","article-title":"Gradientcoin: A peer-to-peer decentralized large language models","author":"Gao","year":"2023","journal-title":"arXiv preprint"},{"key":"ref83","article-title":"A fast optimization view: Reformulating single layer attention in 11 m based on tensor and svm trick, and solving it in matrix multiplication time","author":"Gao","year":"2023","journal-title":"arXiv preprint"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.2307\/2282952"},{"key":"ref85","first-page":"4140","article-title":"Recovery guarantees for one-hidden-layer neural networks","volume-title":"International conference on machine learning. PMLR","author":"Zhong","year":"2017"},{"key":"ref86","article-title":"Learning overparameterized neural networks via stochastic gradient descent on structured data","volume":"31","author":"Li","year":"2018","journal-title":"Advances in neural information processing systems"},{"key":"ref87","article-title":"Gradient descent provably optimizes over-parameterized neural networks","author":"Du","year":"2019","journal-title":"arXiv preprint"},{"key":"ref88","first-page":"242","article-title":"A convergence theory for deep learning via over-parameterization","volume-title":"International Conference on Machine Learning. PMLR","author":"Allen-Zhu","year":"2019"},{"key":"ref89","article-title":"On the convergence rate of training recurrent neural networks","volume":"32","author":"Allen-Zhu","year":"2019","journal-title":"Advances in neural information processing systems"},{"key":"ref90","article-title":"Quadratic suffices for overparametrization via matrix chernoff bound","author":"Song","year":"2019","journal-title":"arXiv preprint"},{"key":"ref91","article-title":"Training multi-layer over-parametrized neural network in subquadratic time","author":"Song","year":"2021","journal-title":"arXiv preprint"},{"key":"ref92","article-title":"Training (overparametrized) neural networks in nearlinear time","author":"Brand","year":"2021","journal-title":"ITCS"},{"key":"ref93","first-page":"16083","article-title":"Bounding the width of neural networks via coupled initialization a worst case analysis","volume-title":"International Conference on Machine Learning. PMLR","author":"Munteanu","year":"2022"},{"key":"ref94","doi-asserted-by":"publisher","DOI":"10.52202\/068431-2217"},{"key":"ref95","article-title":"What learning algorithm is in-context learning? investigations with linear models","author":"Aky\u00fcrek","year":"2022","journal-title":"arXiv preprint"},{"key":"ref96","article-title":"Trained transformers learn linear models in-context","author":"Zhang","year":"2023","journal-title":"arXiv preprint"},{"key":"ref97","article-title":"Large language models are implicitly topic models: Explaning and finding good demonstrations for in-context learning","author":"Wang","year":"2023","journal-title":"arXiv preprint"},{"key":"ref98","article-title":"Task-specific skill localization in fine-tuned language models","author":"Panigrahi","year":"2023","journal-title":"arXiv preprint"},{"key":"ref99","article-title":"Representational strengths and limitations of transformers","author":"Sanford","year":"2023","journal-title":"arXiv preprint"},{"key":"ref100","article-title":"Sparks of artificial general intelligence: Early experiments with gpt-4","author":"Bubeck","year":"2023","journal-title":"arXiv preprint"},{"key":"ref101","article-title":"Gpt-4 technical report","year":"2023","journal-title":"arXiv preprint"},{"key":"ref102","article-title":"A learnable lsh framework for efficient neural network training","volume-title":"International Conference on Learning Representation","author":"Chen","year":"2021"},{"key":"ref103","article-title":"Trainable transformer in transformer","author":"Panigrahi","year":"2023","journal-title":"arXiv preprint"},{"key":"ref104","article-title":"Fine-tuning language models with just forward passes","author":"Malladi","year":"2023","journal-title":"arXiv preprint"},{"key":"ref105","article-title":"Fast quantum algorithm for attention computation","author":"Gao","year":"2023","journal-title":"arXiv preprint"},{"key":"ref106","article-title":"A zeroth-order block coordinate descent algorithm for huge-scale black-box optimization","author":"Cai","year":"2021","journal-title":"arXiv preprint"},{"key":"ref107","article-title":"Direct preference optimization: Your language model is secretly a reward model","author":"Rafailov","year":"2023","journal-title":"arXiv preprint"},{"key":"ref108","article-title":"Sophia: A scalable stochastic second-order optimizer for language model pre-training","author":"Liu","year":"2023","journal-title":"arXiv preprint"}],"event":{"name":"2025 IEEE International Conference on Big Data (BigData)","location":"Macau, China","start":{"date-parts":[[2025,12,8]]},"end":{"date-parts":[[2025,12,11]]}},"container-title":["2025 IEEE International Conference on Big Data (BigData)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx8\/11400704\/11400712\/11400978.pdf?arnumber=11400978","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T06:53:05Z","timestamp":1772866385000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/11400978\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,8]]},"references-count":108,"URL":"https:\/\/doi.org\/10.1109\/bigdata66926.2025.11400978","relation":{},"subject":[],"published":{"date-parts":[[2025,12,8]]}}}