Research map / Large language models / Instruction and fine-tuning
The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that computing the gradient of a one-layer attention loss has the same fine-grained complexity threshold as the forward pass: near-linear time when entries are bounded by o(sqrt(log n)), and SETH-hard beyond that.
Problem
Fine-grained time complexity of the backward (gradient) computation for training attention-based LLMs, and whether it shares the forward-pass threshold on entry magnitude B.
Approach
Derives a closed-form gradient of a one-layer attention regression loss, gives an almost-linear-time algorithm via low-rank polynomial approximation of the attention matrix for B=o(sqrt(log n)), and a SETH-based lower bound for B=omega(sqrt(log n)) by reducing from forward attention hardness through a derivative-based interpolation argument.
Key results
- Gradient of one-layer attention loss computable in n^{1+o(1)} time for d=O(log n) and B=o(sqrt(log n)) up to 1/poly(n) accuracy.
- Assuming SETH, no O(n^{2-q}) algorithm for the gradient problem when B=omega(sqrt(log n)) with d=O(log n).
- Quadratic-time baseline: gradient computable in O(T_mat(n,d,n)+T_mat(n,d,d)) time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use low-rank approximations and tensor techniques for gradient computation | AAttLGC · d = O(log n), B = o(sqrt(log n)) | running time: O(n^2 d^2) -> n^{1+o(1)} | Helped |
| Increase the parameter bound to B = omega(sqrt(log n)) | AAttLGC · d = O(log n), assuming SETH | running time: no algorithm running in time O(n^{2-q}) for any q>0 | Hurt |
Limitations
- Result is for one-layer attention with a simple squared loss, not full multi-layer transformers.
- Y is treated as fixed and gradient taken only with respect to X.
- Upper bound applies only when B=o(sqrt(log n)) and d=O(log n).
Experimental setup
Metrics: running time exponent approximation error
Baselines: naive quadratic gradient computation Hessian-based Newton attention optimization
Builds on: Alman and Song 2023 forward attention complexity polynomial method SETH
Closest papers by meaning
- Language Models as Zero-shot Lossless Gradient Compressors: Towards General Neural Parameter Prior Models (NeurIPS 2024 · similarity 0.89)
- Benchmarking Optimizers for Large Language Model Pretraining (NeurIPS 2026 · similarity 0.89)
- Enhancing Large Language Model Performance with Gradient-Based Parameter Selection (AAAI 2025 · similarity 0.89)
- Building on Efficient Foundations: Effective Training of LLMs with Structured Feedforward Layers (NeurIPS 2024 · similarity 0.88)
- The Journey Matters: Average Parameter Count over Pre-training Unifies Sparse and Dense Scaling Laws (ICLR 2025 · similarity 0.88)
- LoLCATs: On Low-Rank Linearizing of Large Language Models (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.