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

Training large language models (LLMs) involves computationally intensive forward and backward computations. Previous research focused on the forward step, but LLM training efficiency also depends heavily on the speed of backward computation (gradient calculation). The size of the entries in the model’s parameter matrices plays a significant role in determining the training time. This paper addresses the challenges of the backward step, which is significantly more complex than the forward step.

The researchers developed a novel algorithm that efficiently calculates the gradient for the backward step. They also proved that the same computational threshold observed in the forward step exists in the backward step, confirming that the complexity of both forward and backward computations has a similar computational boundary based on matrix entries. This result completely characterizes the fine-grained complexity of LLM training, providing both upper and lower bounds for each training step, which will directly improve LLM training and scalability.