Reverse mode

The identical two-parameter function delivers both slopes in a single backward traversal. Take f(θ1, θ2) = θ1θ2 + θ1 at θ1 = 2, θ2 = 5, so the value is 12. Section 18.2 needed two forward passes to obtain the slopes 6 and 2. Reverse mode begins at the output value, traverses the operations in reverse, and produces both numbers in one traversal.

The walk carries an adjoint beside every node: the rate at which the output changes when that node changes. It starts at the output with a seed of 1, because the output changes with itself at rate one. Each operation then hands its parents a contribution, which is the child's adjoint multiplied by the local slope on that edge. A node with two readers collects two separate contributions, and the [[term:accumulation]]accumulation is their sum. Two readers are a fan-out, and the accumulation is how reverse mode handles it. !The walk starts at $f=12$ with adjoint 1. The product receives that 1 and hands $1\cdot 5=5$ to ${\theta }_1$ and $1\cdot 2=2$ to ${\theta }_2$, while the direct edge hands over $1\cdot 1=1$. ${\theta }_1$ therefore collects $5+1=6$ and ${\theta }_2$ collects 2, both slopes from one traversal. The addition at ${\theta }_1$ is the fan-out: two readers, two contributions. Status: schematic.

The object the walk returns is the vector-Jacobian product: the transpose of the Jacobian applied to the seed. For a scalar loss the seed is one number, and the product is the whole row of partial derivatives. The seed says which combination of outputs you are pricing, and for a loss that combination is the loss itself.

The rule for one node is worth writing once. With ch(j) the children of node j,

That line says: a node's adjoint is the sum, over the nodes that read it, of the reader's adjoint times the local slope between them.

Worked example. Seed the output, so f = 12 has adjoint 1. The product p = θ1θ2 has value 10 and receives 1 from the sum. The product sends 1·5 = 5 to θ1 and 1·2 = 2 to θ2.

The direct edge from θ1 to the sum sends 1·1 = 1, so θ1 collects 5 + 1 = 6. The formula agrees: the slope in θ1 is θ2 + 1 = 6, and the slope in θ2 is θ1 = 2.

A single backward traversal produced both slopes. The count is one backward pass for each output, so a scalar loss needs one pass however many parameters it carries [S:67:267]. Forward mode's count was one pass per input. The two counts are the two dimensions of the same Jacobian, and a loss has one output.

The primitive differentiation rules are brief. A sum hands its adjoint unchanged to both parents, and a product hands the adjoint multiplied by the other factor. An exponential multiplies the incoming adjoint by its own output value, because its derivative is itself. A table with one row per primitive is enough, and the traversal consults that tabulation at every operation [S:66:192]. Nothing in the traversal depends on the magnitude of any formula.

Reverse mode is the transposed version of forward mode. Transposing a product of matrices reverses the order of the factors, which is why the backward traversal reads the operations in reverse. The arithmetic at each operation is the same handful of multiplications, so one backward pass costs roughly what one forward pass costs [S:67:267]. The difference between the modes is the order and the storage, not the local formulas.

The trade becomes dramatic at industrial scale. For a network with a million parameters and one loss, forward mode would need a million passes, and reverse mode needs one. Reverse mode pays for that advantage by keeping the intermediate activations, and the storage grows in proportion to the number of layers.

The principal expense arrives in memory storage. The backward pass multiplies by values the forward pass computed, so those values must still exist when the traversal reaches them [S:67:267]. Reverse mode therefore needs the whole program to run before the backward traversal can start, and it must keep the intermediate outputs [S:65:144]. Depth is paid for in storage capacity, which section 18.5 prices.

There is a second cost, and it is easy to overlook. Because the traversal reads stored values, a stored value that changes after it was saved makes the gradient wrong, with no error and no warning. Section 18.4 turns the record into a data structure, and section 18.6 shows the write that breaks it.

The ordering of the traversal is not a minor detail. Every operation must be visited after the operations that read its output, which is the reverse of the order in which they ran [S:62:303]. That order is what makes each sum complete before the node hands its contributions on. Section 18.4 gives the order a name and proves the property.

The two modes compute the same mathematical object from its two sides. Forward mode multiplies the Jacobian on the right by a direction, and reverse mode multiplies it on the left by a seed. The shapes decide the price: a loss has one output and millions of inputs, so the left multiplication is the inexpensive direction.

Limitation: The one-pass advantage belongs to the output side. A function with many outputs needs one pass per output, and then reverse mode can lose to forward mode. Its memory also grows with depth, which is the problem section 18.5 confronts.

The formal statement. Let $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$ be differentiable at $x$ with Jacobian $J(x)$. Reverse mode computes the vector-Jacobian product $J(x{)}^{\mathsf{T}}u$ for one chosen seed $u\in {\mathbb{R}}^m$ [S:67:267].

Now take a scalar output, written $\ell$, so that $m=1$ and the seed is one number. Take a computation graph with nodes $v_j$, children $\mathrm{ch}(j)$ and local slopes $\partial v_k/\partial v_j$ on each edge. Write ${\bar{v}}_j$ for the adjoint of node $j$. The recursion is

with $\bar{v}=1$ at the output. That line says a node's adjoint is the sum, over the nodes that read it, of the reader's adjoint times the local slope between them.

The claim: if every node is processed after all of its children, the recursion returns ${\bar{v}}_j=\partial \ell /\partial v_j$ at every node. The hypotheses are that the graph is acyclic, that the output is a scalar, and that every local slope on the executed path exists.

The derivation. A directed acyclic graph admits a topological order, in which every node follows its parents. Reversing that order puts every node before its parents, so it is the order the recursion needs.

Induct along the reversed order. The output carries adjoint 1, which is $\partial \ell /\partial \ell$. Take a node $j$ and assume the claim for every child $k$, each of which comes earlier in the reversed order. Every path from $j$ to the output leaves $j$ along exactly one child. The derivative therefore splits into a sum over children, and each term is the derivative along paths through that child times the slope on the edge into it. The first factor is ${\bar{v}}_k$ by the induction hypothesis, the second is the local slope, and their sum is the recursion. So ${\bar{v}}_j$ is the total derivative. Nothing is omitted except the existence of the topological order, which acyclicity supplies.

The edge case. A non-scalar output. Seed with $u=(1,\dots ,1)$ and the pass returns the sum of the rows of $J$, which is the gradient of the sum of the outputs. That is a legitimate quantity and it is not the Jacobian; some libraries make it the default. The core's count, one pass per output, is also the warning: a seed other than a unit vector answers a different question.

A node with no path to the output receives adjoint zero, which is correct and indistinguishable from a node the pass never reached.

What the core hid. The core said reverse mode is the transposed version of forward mode, and used that to explain the reversed order. The precise statement is better. If $\partial f=A_T\cdots A_1$, then $\partial f^{\mathsf{T}}=A_1^{\mathsf{T}}\cdots A_T^{\mathsf{T}}$, so transposition reverses the factors and touches no local rule. The reversal is a property of matrix transposition, not of the program.

Where the analogy breaks. "Walking backwards" suggests running the program in reverse, which would require every step to be invertible. Reverse mode runs on $x^2$, a map with no inverse, and returns $2x$ at the point. The backward pass applies transposed linear maps; it never undoes an operation.

Original sources. Blondel and Roulet state reverse mode as an algorithm that applies the adjoint of each block from the last to the first [S:72:202]. Murphy identifies the same algorithm with backpropagation, a term introduced in the 1980s, and notes that it also arose in control theory as sensitivity analysis [S:62:304]. Bishop derives it as a generalisation of error backpropagation and gives the adjoint recursion as a sum over children [S:67:266].

An open question. Whether one-pass gradients can be had without memory linear in depth, for programs whose blocks are not invertible. Checkpointing reaches logarithmic memory at a growing call cost [S:72:224]. A chain of invertible blocks reaches constant memory, because each input is rebuilt from the next one during the backward pass [S:72:227]. Neither covers a general graph: the reversible case needs invertibility, and the checkpointed case needs a length known in advance.

What would settle it: a schedule family with proved bounds on both calls and slots for non-uniform block costs, demonstrated on a model too large for one device. A method that reports only the memory it saves, and not the calls it spends, has not answered the question.

A frontier result. The Baur-Strassen theorem. For a polynomial $f$, the smallest arithmetic circuit for $\nabla f$ has at most five times the size of the smallest circuit for $f$ [S:72:218]. Blondel and Roulet call this the pillar on which modern machine learning relies, because it makes the cost of a gradient a constant factor above the cost of a value [S:72:230]. That is the precise form of the claim one backward pass makes, and it is what keeps gradient descent affordable at millions of parameters.

What to read next. Blondel and Roulet §8.1.2 for the chain version and §8.3.2 for the circuit version [S:72:202]. Then §8.5 and §8.6 for the two ways of paying the memory bill [S:72:224]. Scardapane's chapter 6 gives the VJP formulation that frameworks implement, in one page [S:65:144].