mlsanityData to 7 Oct 2026

Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time

arXiv 2408.13233 ↗First posted 23 Aug 2024cs.LG cs.AI cs.CLcited by 22

Not on the map. Why?

Abstract (arXiv)

The computational complexity of the self-attention mechanism in popular transformer architectures poses significant challenges for training and inference, and becomes the bottleneck for long inputs. Is it possible to significantly reduce the quadratic time complexity of computing the gradients in multi-layer transformer models? This paper proves that a novel fast approximation method can calculate the gradients in almost linear time n1+o(1) where n is the input sequence length, while it maintains a polynomially small approximation error 1 / poly(n) across the entire model. Our theory holds for general loss functions and when the multi-layer transformer model contains many practical sub-modules, such as residual connection, casual mask, and multi-head attention. By improving the efficiency of gradient computation, we hope that this work will facilitate more effective training and deployment of long-context language models based on our theoretical results.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 109 of its 144 references that are in the map. First posted on arXiv 23 Aug 2024.

Builds on

109 of 144 references.

References · 109

  1. 2017Attention Is All You Needcited by 59,932
  2. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  3. 2023GPT-4 Technical Reportcited by 18,132
  4. 2024The Llama 3 Herd of Modelscited by 14,192
  5. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
  6. 2020Retrieval-Augmented Generation for Knowledge-Intensive NLP Taskscited by 9,160
  7. 2020Score-Based Generative Modeling through Stochastic Differential Equationscited by 8,964
  8. 2017Graph Attention Networkscited by 8,854
  9. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,616
  10. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,530
  11. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  12. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,551
38 more
  1. 2018The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networkscited by 2,250
  2. 2023Retrieval-Augmented Generation for Large Language Models: A Surveycited by 2,185
  3. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,115
  4. 2020Reformer: The Efficient Transformercited by 1,658
  5. 2022Fast Inference from Transformers via Speculative Decodingcited by 1,615
  6. 2023The Rise and Potential of Large Language Model Based Agents: A Surveycited by 1,422
  7. 2022SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Modelscited by 1,338
  8. 2024Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Dualitycited by 1,283
  9. 2023SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shotcited by 1,090
  10. 2015Effective Approaches to Attention-based Neural Machine Translationcited by 1,024
  11. 2024Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Headscited by 821
  12. 2023RWKV: Reinventing RNNs for the Transformer Eracited by 814
  13. 2018SNIP: Single-shot Network Pruning based on Connection Sensitivitycited by 802
  14. 2024Evaluating Very Long-Term Conversational Memory of LLM Agentscited by 800
  15. 2023A Simple and Effective Pruning Approach for Large Language Modelscited by 776
  16. 2023Extending Context Window of Large Language Models via Positional Interpolationcited by 721
  17. 2024MiniCPM: Unveiling the Potential of Small Language Models with Scalable Training Strategiescited by 694
  18. 2020What is the State of Neural Network Pruning?cited by 578
  19. 2021Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networkscited by 521
  20. 2024FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precisioncited by 507
  21. 2020Pruning neural networks without any data by iteratively conserving synaptic flowcited by 475
  22. 2020Picking Winning Tickets Before Training by Preserving Gradient Flowcited by 467
  23. 2023Model Tells You What to Discard: Adaptive KV Cache Compression for LLMscited by 466
  24. 2023Learning to Compress Prompts with Gist Tokenscited by 379
  25. 2022Optimal Brain Compression: A Framework for Accurate Post-Training Quantization and Pruningcited by 317
  26. 2024LayerSkip: Enabling Early Exit Inference and Self-Speculative Decodingcited by 302
  27. 2024Long-context LLMs Struggle with Long In-context Learningcited by 285
  28. 2021Beyond Goldfish Memory: Long-Term Open-Domain Conversationcited by 266
  29. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  30. 2023Compressing Context to Enhance Inference Efficiency of Large Language Modelscited by 185
  31. 2022On The Computational Complexity of Self-Attentioncited by 137
  32. 2023Full Parameter Fine-tuning for Large Language Models with Limited Resourcescited by 134
  33. 2023Focused Transformer: Contrastive Training for Context Scalingcited by 133
  34. 2024The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicrycited by 119
  35. 2024Is A Picture Worth A Thousand Words? Delving Into Spatial Reasoning for Vision Language Modelscited by 111
  36. 2022Long Time No See! Open-Domain Conversation with Long-Term Persona Memorycited by 107
  37. 2022SegViT: Semantic Segmentation with Plain Vision Transformerscited by 105
  38. 2021VLM: Task-agnostic Video-Language Model Pre-training for Video Understandingcited by 102

50 most cited of 109 All 109 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 10; 2025: 11; 2026: 1.

22 papers.

Sort:

By area:

  1. 2024LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformerscited by 35
  2. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  3. 2024Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descentcited by 21
  4. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  5. 2024Looped ReLU MLPs May Be All You Need as Practical Programmable Computerscited by 19
  6. 2024HSR-Enhanced Sparse Attention Accelerationcited by 19
  7. 2025High-Order Matching for One-Step Shortcut Diffusion Modelscited by 15
  8. 2024RoPE Attention Can Be Trained in Almost Linear Timecited by 13
  9. 2024Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformerscited by 12
  10. 2025Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolationcited by 11
  11. 2025On Computational Limits of FlowAR Models: Expressivity and Efficiencycited by 10
  12. 2024Modern Hopfield Networks Require Chain-of-Thought to Solve mathsfNC1-Hard Problemscited by 9
10 more
  1. 2025Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transformcited by 9
  2. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  3. 2024Advancing the Understanding of Fixed Point Iterations in Deep Neural Networks: A Detailed Analytical Studycited by 4
  4. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  5. 2025HOFAR: High-Order Augmentation of Flow Autoregressive Transformerscited by 4
  6. 2025When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?cited by 3
  7. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  8. 2025Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiencycited by 2
  9. 2026GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimizationcited by 1
  10. 2025Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspectivecited by 0