The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
This work addresses the computational bottlenecks in training large language models, providing foundational insights for researchers and practitioners in machine learning, though it is incremental as it extends prior results from forward to backward computations.
The paper tackles the computational complexity of gradient computation for training large language models, showing that it has nearly identical time bounds to forward computation, with no truly sub-quadratic algorithms in certain regimes unless SETH is false, thus fully characterizing the fine-grained complexity of LLM training.
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.