mlsanityData to 7 Oct 2026

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models

arXiv 2402.04497 ↗First posted 7 Feb 2024cs.LG cs.CC cs.CLcited by 30

Not on the map. Why?

Abstract (arXiv)

Large language models (LLMs) have made fundamental contributions over the last a few years. To train an LLM, one needs to alternatingly run `forward' computations and `backward' computations. The forward computation can be viewed as attention function evaluation, and the backward computation can be viewed as a gradient computation. In previous work by [Alman and Song, NeurIPS 2023], it was proved that the forward step can be performed in almost-linear time in certain parameter regimes, but that there is no truly sub-quadratic time algorithm in the remaining parameter regimes unless the popular hypothesis SETH is false. In this work, we show nearly identical results for the harder-seeming problem of computing the gradient of loss function of one layer attention network, and thus for the entire process of LLM training. This completely characterizes the fine-grained complexity of every step of LLM training.

Key facts. Cited by 30 papers in the map (data through 7 Oct 2026). Builds on 58 of its 99 references that are in the map. First posted on arXiv 7 Feb 2024.

Builds on

58 of 99 references.

References · 58

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,084
  5. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
  6. 2019RoBERTa: A Robustly Optimized BERT Pretraining Approachcited by 13,266
  7. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  8. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,304
  9. 2021Prefix-Tuning: Optimizing Continuous Prompts for Generationcited by 3,878
  10. 2022OPT: Open Pre-trained Transformer Language Modelscited by 3,464
  11. 2019XLNet: Generalized Autoregressive Pretraining for Language Understandingcited by 2,801
  12. 2022Emergent Abilities of Large Language Modelscited by 2,483
38 more
  1. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 1,979
  2. 2022LaMDA: Language Models for Dialog Applicationscited by 1,218
  3. 2023SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shotcited by 1,090
  4. 2023A Simple and Effective Pruning Approach for Large Language Modelscited by 776
  5. 2023Fine-Tuning Language Models with Just Forward Passescited by 337
  6. 2019Q8BERT: Quantized 8Bit BERTcited by 296
  7. 2023DNABERT-2: Efficient Foundation Model and Benchmark For Multi-Species Genomecited by 139
  8. 2022On The Computational Complexity of Self-Attentioncited by 137
  9. 2024The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicrycited by 119
  10. 2023Fast Attention Requires Bounded Entriescited by 102
  11. 2023The Expressive Power of Low-Rank Adaptationcited by 100
  12. 2023HyperAttention: Long-context Attention in Near-Linear Timecited by 85
  13. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  14. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  15. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  16. 2017Relative Error Tensor Low Rank Approximationcited by 45
  17. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  18. 2023On Sparse Modern Hopfield Modelcited by 41
  19. 2023Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Modelscited by 37
  20. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  21. 2023STanHop: Sparse Tandem Hopfield Model for Memory-Enhanced Time Series Predictioncited by 35
  22. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  23. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  24. 2023In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trickcited by 32
  25. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  26. 2017Sketching for Kronecker Product Regression and P-splinescited by 29
  27. 2019Optimal Sketching for Kronecker Product Regression and Low Rank Approximationcited by 29
  28. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  29. 2020Kernel Density Estimation through Density Constrained Near Neighbor Searchcited by 26
  30. 2023Differentially Private Attention Computationcited by 25
  31. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  32. 2023Dolfin: Diffusion Layout Transformers without Autoencodercited by 23
  33. 2020Algorithms and Hardness for Linear Algebra on Geometric Graphscited by 22
  34. 2022Training Overparametrized Neural Networks in Sublinear Timecited by 22
  35. 2022A Sublinear Adversarial Training Algorithmcited by 22
  36. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  37. 2018Hardness of Approximate Nearest Neighbor Searchcited by 19
  38. 2022Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimationcited by 19

50 most cited of 58 All 58 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 16; 2025: 12; 2026: 2.

30 papers.

Sort:

By area:

  1. 2024On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)cited by 39
  2. 2024Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Modelscited by 38
  3. 2024Outlier-Efficient Hopfield Layers for Large Transformer-Based Modelscited by 38
  4. 2024Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformerscited by 32
  5. 2024Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Modelscited by 31
  6. 2024Training Tensor Attention Efficiently: From Cubic to Almost Linear Timecited by 29
  7. 2024Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Timecited by 22
  8. 2024HSR-Enhanced Sparse Attention Accelerationcited by 19
  9. 2025T2VWorldBench: A Benchmark for Evaluating World Knowledge in Text-to-Video Generationcited by 18
  10. 2025Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Countingcited by 17
  11. 2024Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyondcited by 15
  12. 2024Provable Differentially Private Computation of the Cross-Attention Mechanismcited by 14
18 more
  1. 2025Quantum Adaptive Self-Attention for Quantum Transformer Modelscited by 14
  2. 2024RoPE Attention Can Be Trained in Almost Linear Timecited by 13
  3. 2025Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolationcited by 11
  4. 2025FZOO: Fast Zeroth-Order Optimizer for Fine-Tuning Large Language Models towards Adam-Scale Speedcited by 11
  5. 2024Towards Infinite-Long Prefix in Transformercited by 10
  6. 2025On Computational Limits of FlowAR Models: Expressivity and Efficiencycited by 10
  7. 2024Modern Hopfield Networks Require Chain-of-Thought to Solve mathsfNC1-Hard Problemscited by 9
  8. 2025Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteriacited by 5
  9. 2024Advancing the Understanding of Fixed Point Iterations in Deep Neural Networks: A Detailed Analytical Studycited by 4
  10. 2025Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questionscited by 4
  11. 2024Unlocking the Theory Behind Scaling 1-Bit Neural Networkscited by 3
  12. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  13. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  14. 2025Unifying Learning Dynamics and Generalization in Transformers Scaling Lawcited by 1
  15. 2024kNN Attention Demystified: A Theoretical Exploration for Scalable Transformerscited by 0
  16. 2025Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspectivecited by 0
  17. 2026Tracking High-order Evolutions via Cascading Low-rank Fittingcited by 0
  18. 2026Beyond Sparse Weights: When Is Attention Compressible?cited by 0