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.

大型语言模型的训练可以通过前向计算和后向计算来实现，前向计算可以被视为注意力函数的评估，后向计算可以被视为梯度计算。本文证明了在某些参数范围内前向计算可以在几乎线性的时间内完成，但在其他参数范围内，除非流行的假设 SETH 是错误的，否则没有真正的次二次时间算法；我们同样在计算单层注意力网络损失函数梯度的更难问题上展示了几乎相同的结果，从而完全揭示了 LLM 训练每个步骤的细粒度复杂性。