Backpropagation › Complexity Analysis

Understanding the computational cost of backpropagation helps explain why it's practical and what the tradeoffs are.

Forward pass cost: Each matrix multiplication $\mathbf{W} \in \mathbb{R}^{m \times n}$ operating on $\mathbf{x} \in \mathbb{R}^n$ costs $O(mn)$ operations. For a network with $L$ layers, the total forward pass cost is $O(\sum_l m_l n_l)$.

Backward pass cost: At each layer, we compute:

• Gradient with respect to weights: another $O(mn)$ operation (outer product)
• Gradient with respect to input: another $O(mn)$ operation (transposed multiply)

The backward pass costs roughly twice the forward pass. This is a fundamental result: computing gradients via backpropagation is only about 2x more expensive than the forward pass, regardless of the number of parameters. In practice, the backward pass is often 2-3x more expensive due to additional memory access patterns and accumulation, but the asymptotic complexity is the same.

Memory cost: The backward pass must store all intermediate activations from the forward pass, because it needs $\mathbf{a}^{(l)}$ to compute gradients at layer $l$. For a mini-batch of size $B$, this costs $O(B \cdot \sum_l m_l)$ memory. This memory requirement explains gradient checkpointing: one can trade computation for memory by not storing all activations, recomputing them as needed during the backward pass. The tradeoff is worth it when GPU memory is the bottleneck, which is common for large language models.

Without backpropagation: Computing gradients naively requires one forward pass per parameter (finite differences), costing $O(P)$ forward passes where $P$ is the number of parameters. For GPT-3's 175 billion parameters, this is completely infeasible. Backpropagation computes all gradients in $O(1)$ forward passes (roughly two), making gradient-based training of large neural networks possible.

The remarkable efficiency of backpropagation: It is worth pausing to appreciate just how extraordinary the 2x constant is. The gradient of a function with $P$ outputs with respect to $N$ inputs generally requires $O(NP)$ work to compute naively. Backpropagation achieves $O(N + P)$ work (essentially just one forward plus one backward pass) specifically because our "function" is a scalar loss and the chain rule lets us share computation across the $N$ outputs. This is the reverse-mode automatic differentiation perspective: it is efficient when there are many inputs and few outputs, which is exactly the case for neural network training where the loss is a single scalar.