What is the computational graph a forward pass records, and in what order does the backward sweep replay it?

## What gets recorded Run a network forward and you execute a sequence of ops: matrix multiplies, additions, nonlinearities, reductions, reshapes. Reverse-mode automatic differentiation records that sequence as a **directed acyclic graph** (DAG). In the convention used here, *ops are nodes and tensors are the edges*: an edge runs from the op that produced a tensor to each op that consumed it. (You will also see the bipartite drawing, with separate circles for tensors and boxes for ops. The two pictures carry the same information; pick one and be consistent when you draw it on a whiteboard.) Three properties of this graph matter. **It is acyclic.** A tensor is produced before it is consumed, so following edges forward can never return you to where you started. Acyclicity is exactly what makes a topological order exist. **It is a record, not a plan.** The graph describes what ran on this input, in this branch of whatever conditional logic the model contains. Feed a different input and a model with data-dependent control flow can record a differently shaped graph. Nothing was compiled ahead of time; the graph is a by-product of execution. **Its nodes carry payload.** A node is not just "a multiply happened here" — it also holds whichever tensor that op's own gradient rule will read back, which is what keeps that tensor alive until the sweep arrives. ## Why the order is reverse topological The backward sweep computes, for each tensor in the graph, the derivative of the scalar loss with respect to that tensor. Call that the tensor's gradient. A node's job during the sweep is: given the gradient of its **output**, produce the gradient of its **inputs**. That phrasing already contains the ordering rule. You cannot run a node's backward step until the gradient of its output exists, and the gradient of its output is produced by the node(s) downstream that consumed it. So every consumer must be processed first. That is precisely the definition of reverse topological order: visit a node only after all nodes reachable from it have been visited. Start at the loss, which is a scalar and whose gradient with respect to itself is 1. From there the sweep proceeds outward against the direction of the forward edges, each node handing its input gradients to the nodes that fed it. If you violated the order — visited some node before an op that consumed its output — you would be asking for a multiplication by a quantity that has not been computed. There is no sensible default to substitute; the sweep would simply be wrong. ## Reverse tape order versus reverse topological order A convenient implementation trick: because ops are appended in execution order, the recorded sequence is *already* a topological order. Reversing that list therefore gives a valid reverse topological order, with no graph algorithm required. This is why a straight-line chain like `x -> linear -> tanh -> linear -> loss` needs nothing more than popping records off the end of a tape. Be careful with the phrasing though. Reverse-recording order is *a* valid order, not *the* order. Many valid orders exist for a branching graph, and any of them produce identical results. ## Reading the order off a branching graph Take a two-tower retrieval scorer. One branch encodes the query into a vector, an entirely separate branch encodes the document into a vector, and the two meet at a single dot-product node that produces the score fed to the loss. Drawn out, the graph is a diamond that opens at the two inputs and closes at the dot product. What does the reverse sweep have to do? 1. The loss node first — it is the only consumer of the score. 2. Then the dot-product node, which is the only consumer of both tower outputs. It produces the gradient of the query vector and the gradient of the document vector. 3. Then the two towers. They are independent of each other: no edge runs between them, so the sweep may finish the query tower and then the document tower, or the other way, or interleave them layer by layer. All three orders are legal reverse topological orders and give the same numbers. The useful takeaway for a whiteboard question is that reverse topological order is a **partial** constraint, not a single sequence. It pins down what must come before what, and leaves everything else free. ## Why reverse and not forward Reverse-mode is the direction that suits training. One sweep backward from a single scalar loss yields the gradient with respect to *every* node in the graph at a cost proportional to one forward pass. Sweeping the other direction — propagating derivatives forward from the inputs — gives you the derivative of everything with respect to *one* input at a time, which is the wrong shape of answer when a model has a huge number of parameters and one scalar loss. ## What to be able to draw Given a small expression, draw the DAG, mark the loss, and annotate each node with the arrow direction of the sweep. Being able to state "this node cannot be visited until that one has been, because it consumes its output" is the whole of the ordering rule.