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 .
- 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 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 , where is the identity except for one row holding the . The two modes are the two ways of multiplying this product by a vector.
Forward mode pushes a tangent through the program alongside the values, in evaluation order. It computes a Jacobian–vector product (JVP):
Algebraically, forward mode evaluates on dual numbers with , because for every smooth elementary :
Reverse mode first runs the program forward and records the trace (the tape), then propagates adjoints 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):
A full Jacobian takes JVPs (one per input direction) or VJPs (one per output). For a loss, , and one reverse sweep yields the whole gradient: reverse mode applied to a network is backpropagation. Forward mode wins when , such as a few parameters driving a large simulation.
| Mode | One sweep computes | Sweeps for a full Jacobian | Extra memory |
|---|---|---|---|
| Forward (tangent) | , a JVP | one tangent per live value | |
| Reverse (adjoint) | , a VJP | the tape, values |
You need the full Jacobian of , say ten design parameters of a simulation with a million outputs. Which mode, and roughly how many sweeps?
- Reverse mode, one sweep
- Reverse mode, sweeps
- Forward mode, 10 sweeps
- Either mode, one sweep
Show the answer
C. Forward mode, 10 sweeps
Forward mode computes one column per sweep, so 10 sweeps give all entries. Reverse mode gets one row per sweep and would need . Reverse mode wins only when the outputs are few, as for a scalar loss.
The cheap-gradient principle
Forward sweep: evaluate the trace and store each that some local partial will need. Each operation costs at least one unit:
Reverse sweep: visit once. For each argument , compute from stored values and do one multiply-add into . That is work per argument, so at most a constant multiple of :
Summing over nodes, the reverse sweep costs at most times the forward sweep, whatever is. Each input's partial is read off at the end as (with ):
The hidden cost is space. The reverse sweep needs forward values in reverse order, so the tape holds numbers: proportional to the running time of , not to the memory that evaluating needs. For a network that means every activation of every layer.
The principle is special to gradients of scalar functions. A full Jacobian costs sweeps, and finding the cheapest way to accumulate a general Jacobian from its elementary partials is NP-complete (Naumann, 2008). A full Hessian costs 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 steps : the layers of a network, or the time steps of a simulation or an RNN. The reverse sweep needs the states in reverse order, . Storing all of them costs states; storing only and recomputing each state from it costs steps. Checkpointing stores a few states and recomputes the others from the nearest checkpoint. Its best possible trade-off is known exactly.
Let be the maximum. If no advances are left (), only the step leaving the state at hand can be reversed. The same holds when no slot at all is left to keep anything (, the boundary case the recursion below reaches):
Otherwise an optimal schedule first advances from to some and keeps it. The tail after must then be reversed with one slot fewer (the slot of stays occupied) but with its steps' full budget of advances:
Afterwards the slot of is free again, but every step of the head has already been advanced once:
Choosing to make both tight gives Pascal's rule, and with the boundary values the binomial coefficient:
With slots and repetition number , how many steps can be reversed at most?
Show the answer
20
. For comparison, storing every state would need 20 slots, and a single slot, recomputing from the start each time, would need , since .
Two corollaries. With , , so memory and advances per step suffice: 8 slots and 8 advances reverse steps. With , , so about 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 gives a Hessian–vector product for a constant multiple of the cost of (Pearlmutter, 1994):
Implicit differentiation. Some layers are defined by a condition rather than a program: a fixed point , 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, . 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 alongside the values; reverse mode computes VJPs in a backward sweep, summing adjoints at fan-outs.
- Cheap-gradient principle: for scalar , reverse mode delivers the whole gradient for a constant multiple (about 3 to 5) of the cost of , independent of the number of inputs. The price is a tape proportional to the running time.
- Full Jacobians cost sweeps, and optimal Jacobian accumulation is NP-complete; a Hessian–vector product costs by forward-over-reverse.
- Checkpointing with slots and repetition number reverses steps: logarithmic memory for logarithmic recomputation, or memory for one extra forward pass.
- AD differentiates programs, not functions: at kinks it can return values that are not derivatives, as shows.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
A network's loss takes floating-point operations to evaluate on a batch. Roughly how many does its gradient with respect to all parameters cost by reverse mode?
- About , one forward evaluation per parameter
- About , a small constant times the forward cost
- About , the forward cost with no overhead
- About , the forward cost squared
Show the answer
B. About , 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. is the cost of finite differences.
Why does reverse mode need memory proportional to the number of operations, while forward mode does not?
- Because adjoints must be stored in double precision
- Because one reverse sweep computes the full Jacobian
- 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
- 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 . The adjoint sweep runs backward, and the local partials need forward values computed long ago. Checkpointing trades this memory for recomputation.
What does one Hessian–vector product for cost by forward-over-reverse AD?
- gradient evaluations
- operations, to form the Hessian first
- A constant multiple of the cost of evaluating
- It cannot be computed exactly, only approximated by finite differences
Show the answer
C. A constant multiple of the cost of evaluating
The gradient is a program costing , and one forward-mode JVP of that program along costs another constant factor (Pearlmutter, 1994). The full Hessian, by contrast, needs such products.
For a chain of layers, you store a checkpoint every layers and recompute each segment during the backward pass. About how much memory and extra compute does this need?
- stored states and about one extra forward pass
- stored states and no extra computation
- stored states and no extra computation
- stored states and extra computation
Show the answer
A. stored states and about one extra forward pass
checkpoints plus one recomputed segment of states give memory, and each layer is recomputed once: one extra forward pass in total. Binomial schedules go further, to memory at 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).