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

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 …

attention complexity computation cs.cc cs.cl cs.ds cs.lg evaluation fine-grained function gradient language language models large language large language models llm llms train training