The tape and the graph

A program executes once and returns 64. A moment later the training step asks for the slope of that answer with respect to the input, and the numbers the program used are no longer available. Several were overwritten by subsequent computation. A differentiating implementation must determine, before it can answer, what to keep.

The record is called a trace: the ordered list of operations that actually ran, together with the values each operation read. An implementation that merely appends to a list is called a tape. The list is not a symbolic formula unrolled into a tree structure. A value used twice gets one entry and two readers, and that sharing is what maintains the record proportional to the operations rather than increasing through duplication [S:66:186]. !The tape on the left lists the four operations in the order they ran; the diamond on the right draws the same four operations as nodes and edges. Because $x$, $a$ and $t$ are each read twice, the diamond has six edges, and the backward walk contributes along each one separately: $8+8=16$ at $t$, $16+16=32$ at $a$, and $64+64=128$ at $x$. The closed form agrees, since $L=4x^4$ has slope $16x^3=128$ at $x=2$. Status: schematic.

The identical object depicted with nodes and arrows is a computation graph. Each node contains a value, each arrow says which operation read which node, and a node with two outgoing arrows is a fan-out. The graph need not be a linear chain. Branches, sums and shared subexpressions all fit, and the backward traversal processes one edge at a time [S:66:187].

Three implementations differ in layout and agree in content. One takes a graph with numerical values and returns numerical gradient values [S:66:190-191].

Another builds a graph for the derivatives, which can itself be differentiated again [S:66:190-191]. A third appends a plain list. All three answer the same question: which operation produced this value, and what did it read? The trace is the content, and the tape is one shape of that content.

Worked example. Take x = 2, then a = x·x = 4, then t = a + a = 8, then L = t·t = 64. The trace has four entries, and x, a and t are each read twice.

Seed L with 1. The square L = t·t has local slope 8 on each of its two edges, so t receives 8 + 8 = 16. The sum t = a + a has slope 1 on each edge, so a receives 16 + 16 = 32. The square a = x·x has slope x = 2 on each edge, so x receives 64 + 64 = 128. The closed form checks the result, because L = 4x^4 and its slope is 16x^3 = 128 at x = 2.

That line says the four-node computation graph and the single algebraic formula describe the same function, and the sweep agrees with the formula.

The record must contain more than the intermediate outputs. For the product, the backward rule needs the other factor, which is an input to the operation. For the exponential and the hyperbolic tangent, the rule reads the operation's own output. A flat column of numerical results says neither which operation read which value nor what the other factor was, so it cannot support the sweep.

A tree would give every read its own copy of the subexpression. The chain f(f(f(w))) offers two records: store the shared value once, or recompute it at every use [S:66:186]. The first record is shorter and faster, and the second is useful when memory is scarce. That choice is checkpointing in miniature form, and section 18.5 transforms it into a tunable dial.

The additions are the complete cost of sharing. A chain has one reader per node, so no sum is needed. A fan-out has several readers, and each sends a separate contribution [S:66:191]. An implementation that assigns instead of adding keeps one contribution, and the number it reports looks entirely reasonable.

The diamond has four nodes and six edges, because x, a and t are each read twice. The backward sweep visits every edge once, so it performs six local multiplications and no more [S:66:187]. The count is linear in the number of edges, and linearity is the reason a deep model remains trainable at all.

The order of the replay is the reverse of a topological order, a listing in which every node comes after the nodes that feed it. Sweeping in the recorded order instead visits x before anything has contributed to it, and the answer is 0. The arithmetic never changes between the two runs, and the order does [S:62:303]. Without a record of which operations read which values, no sweep could establish that order at all.

Storage capacity is the principal expense. Every value the backward traversal multiplies by must remain available, so the trace holds one slot per node the sweep will read [S:67:267]. At four nodes that is trivial. At a thousand layers it becomes the central engineering problem, and section 18.5 is about buying it back.

Limitation: The record is only valid while it remains factually accurate. A stored value that is overwritten after it was saved is a different number when the sweep arrives, and the gradient becomes incorrect without any diagnostic. The trace is a promise about the past, and nothing in the arithmetic enforces that implicit promise.

The formal statement. A trace of one run is a finite sequence of records $r_t=({\text{op}}_t,{\text{inputs}}_t,{\text{output}}_t)$, one per operation the run performed [S:66:186]. The computation graph is the directed acyclic graph whose nodes are the recorded values and whose edges are the input relations the records name. A node read by more than one operation is a fan-out. The replay is a walk over the nodes in an order that reverses a topological order, accumulating at each node the sum over its readers.

The theorem: the replay returns $\partial \ell /\partial v_j$ at every node $j$, at a cost of one local multiplication and one addition per edge [S:66:187]. The hypotheses are that the graph is acyclic, that the recorded values are the values the run used, and that each local slope exists.

The derivation. Two steps, the first stated without proof in the core.

First, the recorded order of a sequential program is already a topological order. A value is recorded only after the values the operation read, so every edge points forward in recorded time. Reversing the recorded order therefore visits every node before its parents, which is the order the replay needs. This is why a list suffices: no sorting step is needed when the program ran one operation at a time [S:66:186].

Second, on that order the argument of 18.3 applies edge by edge. Each edge contributes one product, each fan-out one sum, and the total is the sum over paths, which is what the chain rule gives. The cost is linear in the number of edges because each edge is visited once [S:66:187].

One step is omitted. A loop in the program text does not make the graph cyclic, because the run unrolls it. The acyclicity hypothesis is about the trace, not about the source.

The edge case. The trace is a value, not a type. Run the same program on an input that changes the trip count of a while loop, and the graph has a different shape and a different number of edges. The derivative the replay returns is the derivative of the executed path, so at the input where the count changes the derivative jumps. A formula for the same function would have one derivative there, or none.

The core's opening, "a program executes once and returns 64", carries more than it appears to: the record is of one execution.

What the core hid. The core said the graph need not be a linear chain, and that the tape is one shape of the same content. What it hid is why the two are interchangeable. For a sequential program the recorded order is topological, so a list is enough. A parallel program can record operations with no total order between them, and then a list is not enough: you need the graph, or an ordering pass.

Where the analogy breaks. "The computer remembers what it did" suggests a memory of the program. It remembers one run. Two runs of the same text produce two traces, and nothing in either trace says they came from the same source. That is also why the trace can be right about a program that computes the wrong function.

Original sources. Goodfellow, Bengio and Courville define the computational graph, order its nodes so each can be computed in turn, and add a backward subgraph with one node per forward node whose computation runs in exactly the reverse order [S:66:186]. The same chapter states that the cost scales linearly with the number of edges [S:66:187]. Murphy states the fan-out rule as a sweep in topological order with a sum of partial VJPs over outgoing edges [S:62:303].

An open question. What derivative a program with an unbounded loop has. Such a program has no fixed graph, so to differentiate it at all an implementation truncates the loop after a fixed number of iterations and unrolls the result [S:72:168]. Whether the truncated run returns the derivative of the function the program denotes, rather than of the prefix that happened to run, is not settled in general.

What would settle it: a semantics for a core language with unbounded loops, in which every program has a defined derivative. The semantics must come with a proof that the derivative agrees with finite differences on a test suite that exercises early exit, recursion and aliasing. A library that covers the loops its users happen to write has not settled the question.

A frontier result. Symbol-to-symbol differentiation. Instead of returning numbers, the engine adds nodes to the graph that describe how to compute the derivative, so the derivative is itself a graph [S:66:190-191]. The same engine can then differentiate that graph again, which is how higher derivatives come from one mechanism. The cost is stated in the same chapter: a graph with $n$ nodes needs at most $O(n^2)$ operations, and a chain-structured graph needs $O(n)$ [S:66:194].

What to read next. Goodfellow §6.5.5 and §6.5.6 for the two implementation styles and the general algorithm with its cost bound [S:66:194]. Blondel and Roulet §8.3 for the circuit formulation and the fan-out argument [S:72:211]. Then Dive into Deep Learning §2.5, where the same objects appear as the attributes a library exposes, including the buffer that accumulates rather than replaces [S:69:100].