Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Automatic Differentiation

Forward and reverse mode, and computational graphs.

Every deep-learning framework contains a small compiler that turns your forward code into its derivative. It rests on one theorem: the gradient of a scalar function costs only a small constant times as much as the function itself, however many inputs there are. The catch is memory, and managing it turns out to be an algorithmic problem with a surprisingly exact answer.

What you’ll learn

  • Define evaluation traces and compute Jacobian–vector and vector–Jacobian products by forward and reverse mode, with their costs for f:Rn→Rmf:\R^n\to\R^m.
  • State and prove the cheap-gradient principle (Baur–Strassen; Griewank), and explain why it does not extend to full Jacobians or Hessians.
  • Derive the binomial checkpointing bound β(s,r)=(s+rs)\beta(s,r)=\binom{s+r}{s} and the logarithmic memory–recomputation trade-off it implies.
  • Compute Hessian–vector products by forward-over-reverse differentiation, and recognize where differentiating a nonsmooth program returns a wrong derivative.

Evaluation traces, tangents and adjoints

Automatic differentiation (AD) applies the chain rule to the trace: exactly, unlike finite differences, and without building symbolic expressions. Writing each operation as a map on the whole state gives f′(x)=AK⋯A2A1f'(\mathbf x)=A_K\cdots A_2A_1, where AiA_i is the identity except for one row holding the cijc_{ij}. The two modes are the two ways of multiplying this product by a vector.

DerivationForward and reverse mode
  1. v˙i=∑j≺icij v˙j⟹y˙=f′(x) x˙=AK(⋯(A1x˙))\dot v_i=\sum_{j\prec i}c_{ij}\,\dot v_j\qquad\Longrightarrow\qquad\dot{\mathbf y}=f'(\mathbf x)\,\dot{\mathbf x}=A_K\big(\cdots\big(A_1\dot{\mathbf x}\big)\big)

    Forward mode pushes a tangent x˙\dot{\mathbf x} through the program alongside the values, in evaluation order. It computes a Jacobian–vector product (JVP):

  2. (a+bε)(c+dε)=ac+(ad+bc) ε,sin⁡(a+bε)=sin⁡a+bcos⁡a  ε(a+b\varepsilon)(c+d\varepsilon)=ac+(ad+bc)\,\varepsilon,\qquad\sin(a+b\varepsilon)=\sin a+b\cos a\;\varepsilon

    Algebraically, forward mode evaluates ff on dual numbers a+bεa+b\varepsilon with ε2=0\varepsilon^2=0, because g(a+bε)=g(a)+g′(a) b εg(a+b\varepsilon)=g(a)+g'(a)\,b\,\varepsilon for every smooth elementary gg:

  3. vˉj=∑i: j≺ivˉi cij⟹xˉ⊤=yˉ⊤f′(x)=((yˉ⊤AK)⋯)A1\bar v_j=\sum_{i:\,j\prec i}\bar v_i\,c_{ij}\qquad\Longrightarrow\qquad\bar{\mathbf x}^\top=\bar{\mathbf y}^\top f'(\mathbf x)=\big(\big(\bar{\mathbf y}^\top A_K\big)\cdots\big)A_1

    Reverse mode first runs the program forward and records the trace (the tape), then propagates adjoints vˉj=∂(yˉ⊤y)/∂vj\bar v_j=\partial(\bar{\mathbf y}^\top\mathbf y)/\partial v_j from the outputs back. A variable used by several operations collects one term from each, so fan-out becomes a sum. It computes a vector–Jacobian product (VJP):

  4. cost⁡(f′(x))≈min⁡(n,m)×cost⁡(f)×a small constant\operatorname{cost}\big(f'(\mathbf x)\big)\approx\min(n,m)\times\operatorname{cost}(f)\times\text{a small constant}

    A full Jacobian takes nn JVPs (one per input direction) or mm VJPs (one per output). For a loss, m=1m=1, and one reverse sweep yields the whole gradient: reverse mode applied to a network is backpropagation. Forward mode wins when n≪mn\ll m, such as a few parameters driving a large simulation.

ModeOne sweep computesSweeps for a full JacobianExtra memory
Forward (tangent)f′(x)x˙f'(\mathbf x)\dot{\mathbf x}, a JVPnnone tangent per live value
Reverse (adjoint)yˉ⊤f′(x)\bar{\mathbf y}^\top f'(\mathbf x), a VJPmmthe tape, O(K)\order{K} values
For a network's loss, nn is the number of parameters (up to about 101210^{12} in the mid-2020s) and m=1m=1.
Check your understanding

You need the full Jacobian of f:R10→R106f:\R^{10}\to\R^{10^6}, say ten design parameters of a simulation with a million outputs. Which mode, and roughly how many sweeps?

  1. Reverse mode, one sweep
  2. Reverse mode, 10610^6 sweeps
  3. Forward mode, 10 sweeps
  4. Either mode, one sweep
Show the answer

C. Forward mode, 10 sweeps

Forward mode computes one column f′(x)ejf'(\mathbf x)\mathbf e_j per sweep, so 10 sweeps give all 10710^7 entries. Reverse mode gets one row per sweep and would need 10610^6. Reverse mode wins only when the outputs are few, as for a scalar loss.

The cheap-gradient principle

DerivationProof sketch
  1. forward work=∑i=1Kcost⁡(ϕi)\text{forward work}=\sum_{i=1}^K\operatorname{cost}(\phi_i)

    Forward sweep: evaluate the trace and store each viv_i that some local partial will need. Each operation costs at least one unit:

  2. vˉj+=vˉi cijfor each j≺i,work at node i≤c⋅cost⁡(ϕi)\bar v_j\mathrel{+}=\bar v_i\,c_{ij}\quad\text{for each }j\prec i,\qquad\text{work at node }i\le c\cdot\operatorname{cost}(\phi_i)

    Reverse sweep: visit i=K,…,1i=K,\dots,1 once. For each argument j≺ij\prec i, compute cijc_{ij} from stored values and do one multiply-add into vˉj\bar v_j. That is O(1)\order{1} work per argument, so at most a constant multiple of cost⁡(ϕi)\operatorname{cost}(\phi_i):

  3. ops⁡(f,∇f)≤(1+c)ops⁡(f)=ωops⁡(f)\operatorname{ops}(f,\nabla f)\le(1+c)\operatorname{ops}(f)=\omega\operatorname{ops}(f)

    Summing over nodes, the reverse sweep costs at most cc times the forward sweep, whatever nn is. Each input's partial is read off at the end as xˉj=∂f/∂xj\bar x_j=\partial f/\partial x_j (with yˉ=1\bar y=1):

  4. mem⁡(f,∇f)=O(ops⁡(f))versusmem⁡(f) for evaluating f\operatorname{mem}(f,\nabla f)=\order{\operatorname{ops}(f)}\qquad\text{versus}\qquad\operatorname{mem}(f)\ \text{for evaluating }f

    The hidden cost is space. The reverse sweep needs forward values in reverse order, so the tape holds O(K)\order{K} numbers: proportional to the running time of ff, not to the memory that evaluating ff needs. For a network that means every activation of every layer.

The principle is special to gradients of scalar functions. A full Jacobian costs min⁡(n,m)\min(n,m) sweeps, and finding the cheapest way to accumulate a general Jacobian from its elementary partials is NP-complete (Naumann, 2008). A full Hessian costs nn sweeps of a second-order method. A single Hessian–vector product, though, is cheap again (step 4).

Trading memory for time: checkpointing

Consider a chain of LL steps sk+1=Fk(sk)\mathbf s_{k+1}=F_k(\mathbf s_k): the layers of a network, or the time steps of a simulation or an RNN. The reverse sweep needs the states in reverse order, sL−1,…,s0\mathbf s_{L-1},\dots,\mathbf s_0. Storing all of them costs LL states; storing only s0\mathbf s_0 and recomputing each state from it costs O(L2)\order{L^2} steps. Checkpointing stores a few states and recomputes the others from the nearest checkpoint. Its best possible trade-off is known exactly.

DerivationProof of the recursion
  1. β(s,0)=β(0,r)=1\beta(s,0)=\beta(0,r)=1

    Let β(s,r)\beta(s,r) be the maximum. If no advances are left (r=0r=0), only the step leaving the state at hand can be reversed. The same holds when no slot at all is left to keep anything (s=0s=0, the boundary case the recursion below reaches):

  2. L−l^≤β(s−1,r)L-\hat l\le\beta(s-1,r)

    Otherwise an optimal schedule first advances from s0\mathbf s_0 to some sl^\mathbf s_{\hat l} and keeps it. The tail after l^\hat l must then be reversed with one slot fewer (the slot of s0\mathbf s_0 stays occupied) but with its steps' full budget of rr advances:

  3. l^≤β(s,r−1)\hat l\le\beta(s,r-1)

    Afterwards the slot of sl^\mathbf s_{\hat l} is free again, but every step of the head has already been advanced once:

  4. β(s,r)=β(s−1,r)+β(s,r−1)⟹β(s,r)=(s+rs)\beta(s,r)=\beta(s-1,r)+\beta(s,r-1)\quad\Longrightarrow\quad\beta(s,r)=\binom{s+r}{s}

    Choosing l^\hat l to make both tight gives Pascal's rule, and with the boundary values the binomial coefficient:

Predict before you look

With s=3s=3 slots and repetition number r=3r=3, how many steps can be reversed at most?

Show the answer

20

β(3,3)=(63)=20=β(2,3)+β(3,2)=10+10\beta(3,3)=\binom{6}{3}=20=\beta(2,3)+\beta(3,2)=10+10. For comparison, storing every state would need 20 slots, and a single slot, recomputing from the start each time, would need r=19r=19, since β(1,r)=r+1\beta(1,r)=r+1.

Two corollaries. With s=rs=r, β=(2ss)≈4s/πs\beta=\binom{2s}{s}\approx4^s/\sqrt{\pi s}, so O(log⁡L)\order{\log L} memory and O(log⁡L)\order{\log L} advances per step suffice: 8 slots and 8 advances reverse (168)=12,870\binom{16}{8}=12{,}870 steps. With r=2r=2, β(s,2)=(s+22)≈s2/2\beta(s,2)=\binom{s+2}{2}\approx s^2/2, so about 2L\sqrt{2L} slots and roughly one extra forward pass suffice, the scheme Chen, Xu, Zhang & Guestrin (2016) popularized for training deep networks with sublinear memory. Two further escapes: reversible layers, whose inputs can be reconstructed exactly from their outputs (RevNets, Gomez et al., 2017), and selective recomputation of cheap operations, such as activation functions but not matrix products, standard in large-transformer training.

Higher derivatives, implicit layers and kinks

JVPs and VJPs are themselves programs, so the modes compose. Differentiating the gradient program in forward mode along v\mathbf v gives a Hessian–vector product for a constant multiple of the cost of ff (Pearlmutter, 1994):

∇2f(x) v=ddϵ∇f(x+ϵv)∣ϵ=0=JVP(∇f; x, v),ops⁡=O(ops⁡(f))\nabla^2f(\mathbf x)\,\mathbf v=\frac{d}{d\epsilon}\nabla f(\mathbf x+\epsilon\mathbf v)\Big|_{\epsilon=0}=\mathrm{JVP}\big(\nabla f;\ \mathbf x,\ \mathbf v\big),\qquad\operatorname{ops}=\order{\operatorname{ops}(f)}
Forward-over-reverse. Power iteration or Lanczos on these products estimates the top Hessian eigenvalues of a network with millions of weights, the sharpness of Loss Landscapes & Initialization, without ever forming the P×PP\times P Hessian. Hutchinson's estimator E[v⊤∇2f v]=tr⁡∇2f\E[\mathbf v^\top\nabla^2f\,\mathbf v]=\operatorname{tr}\nabla^2f, for random v\mathbf v with E[vv⊤]=I\E[\mathbf v\mathbf v^\top]=I, estimates its trace.

Implicit differentiation. Some layers are defined by a condition rather than a program: a fixed point z⋆=g(z⋆,θ)\mathbf z^\star=g(\mathbf z^\star,\boldsymbol\theta), as in deep equilibrium models (Bai, Kolter & Koltun, 2019), or the solution of an optimization problem (OptNet, Amos & Kolter, 2017). The implicit function theorem gives the derivative without differentiating through the solver's iterations, ∂z⋆/∂θ=(I−∂zg)−1∂θg\partial\mathbf z^\star/\partial\boldsymbol\theta=(I-\partial_{\mathbf z}g)^{-1}\partial_{\boldsymbol\theta}g. A VJP with it costs one linear solve, and memory independent of the number of solver steps.

Key takeaways

  • AD differentiates an evaluation trace exactly. Forward mode computes JVPs f′(x)x˙f'(\mathbf x)\dot{\mathbf x} alongside the values; reverse mode computes VJPs yˉ⊤f′(x)\bar{\mathbf y}^\top f'(\mathbf x) in a backward sweep, summing adjoints at fan-outs.
  • Cheap-gradient principle: for scalar ff, reverse mode delivers the whole gradient for a constant multiple (about 3 to 5) of the cost of ff, independent of the number of inputs. The price is a tape proportional to the running time.
  • Full Jacobians cost min⁡(n,m)\min(n,m) sweeps, and optimal Jacobian accumulation is NP-complete; a Hessian–vector product costs O(ops⁡(f))\order{\operatorname{ops}(f)} by forward-over-reverse.
  • Checkpointing with ss slots and repetition number rr reverses (s+rs)\binom{s+r}{s} steps: logarithmic memory for logarithmic recomputation, or O(L)\order{\sqrt L} memory for one extra forward pass.
  • AD differentiates programs, not functions: at kinks it can return values that are not derivatives, as ReLU(x)−ReLU(−x)\mathrm{ReLU}(x)-\mathrm{ReLU}(-x) shows.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A network's loss takes 101010^{10} floating-point operations to evaluate on a batch. Roughly how many does its gradient with respect to all 10810^8 parameters cost by reverse mode?

  1. About 101810^{18}, one forward evaluation per parameter
  2. About 3×10103\times10^{10}, a small constant times the forward cost
  3. About 101010^{10}, the forward cost with no overhead
  4. About 102010^{20}, the forward cost squared
Show the answer

B. About 3×10103\times10^{10}, a small constant times the forward cost

The reverse sweep costs a small constant times the forward work, independent of the number of parameters. For dense layers the backward pass is two matrix products per forward product, about 3 forward passes in total. 101810^{18} is the cost of finite differences.

Question 2

Why does reverse mode need memory proportional to the number of operations, while forward mode does not?

  1. Because adjoints must be stored in double precision
  2. Because one reverse sweep computes the full Jacobian
  3. Because the reverse sweep visits operations in the opposite order of evaluation and needs each operation's inputs, so they must be stored or recomputed
  4. Because the tape stores the derivative of every operation with respect to every input
Show the answer

C. Because the reverse sweep visits operations in the opposite order of evaluation and needs each operation's inputs, so they must be stored or recomputed

Forward mode propagates tangents in evaluation order, so each value can be discarded after its last use, exactly as when evaluating ff. The adjoint sweep runs backward, and the local partials cijc_{ij} need forward values computed long ago. Checkpointing trades this memory for recomputation.

Question 3

What does one Hessian–vector product ∇2f(x)v\nabla^2f(\mathbf x)\mathbf v for f:Rn→Rf:\R^n\to\R cost by forward-over-reverse AD?

  1. O(n)\order{n} gradient evaluations
  2. O(n2)\order{n^2} operations, to form the Hessian first
  3. A constant multiple of the cost of evaluating ff
  4. It cannot be computed exactly, only approximated by finite differences
Show the answer

C. A constant multiple of the cost of evaluating ff

The gradient is a program costing O(ops⁡(f))\order{\operatorname{ops}(f)}, and one forward-mode JVP of that program along v\mathbf v costs another constant factor (Pearlmutter, 1994). The full Hessian, by contrast, needs nn such products.

Question 4

For a chain of LL layers, you store a checkpoint every L\sqrt L layers and recompute each segment during the backward pass. About how much memory and extra compute does this need?

  1. O(L)\order{\sqrt L} stored states and about one extra forward pass
  2. O(log⁡L)\order{\log L} stored states and no extra computation
  3. O(L)\order{L} stored states and no extra computation
  4. O(1)\order{1} stored states and O(L2)\order{L^2} extra computation
Show the answer

A. O(L)\order{\sqrt L} stored states and about one extra forward pass

L\sqrt L checkpoints plus one recomputed segment of L\sqrt L states give O(L)\order{\sqrt L} memory, and each layer is recomputed once: one extra forward pass in total. Binomial schedules go further, to O(log⁡L)\order{\log L} memory at O(log⁡L)\order{\log L} recomputations per step.

Further reading

  • W. Baur & V. Strassen, "The complexity of partial derivatives," Theoretical Computer Science 22, 317–330 (1983).
  • A. Griewank & A. Walther, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, 2nd ed. (SIAM, 2008).
  • A. Griewank & A. Walther, "Algorithm 799: revolve: an implementation of checkpointing for the reverse or adjoint mode of computational differentiation," ACM Transactions on Mathematical Software 26(1) (2000).
  • B. A. Pearlmutter, "Fast exact multiplication by the Hessian," Neural Computation 6(1), 147–160 (1994).
  • A. G. Baydin, B. A. Pearlmutter, A. A. Radul & J. M. Siskind, "Automatic differentiation in machine learning: a survey," Journal of Machine Learning Research 18 (2018).