Explainer Library

Deep learning foundations

Interactive explainer

Why backpropagation needs an order

A gradient can move through a node only after every downstream path has contributed to that node. Topological sorting gives us exactly that safe schedule.

Step through one real scalar graph. Watch the recursive calls build a dependency-first list, then reverse it once for backpropagation.

  1. 01Follow each saved ParentLink to an operand.
  2. 02Append a node only after its parents return.
  3. 03Reverse the finished list for backward.

Interactive trace · exact notebook graph

Watch dependency_safe_order(L) build its list

Each step is one action performed by the recursive helper. The graph is fixed; only the call stack, seen, and safe_order change.

Step 0 of 0
Ready
Press Next or Play to call append_after_parents(L).
Computation graph used by the dependency-order trace The forward graph has leaves w and x creating m, m and b creating a, a and y creating e, and e creating L. The recursive traversal follows those edges in reverse, from each output to its parent operands. wleaf · value 2 xleaf · value 3 mw × x = 6 bleaf · value 1 am + b = 7 yleaf · value 10 ea − y = −3 Le² = 9 forward graph: operands → outputs   ·   traversal: output → saved parent operand

The moving dashed edge is a saved ParentLink being followed from an output back to one direct operand. On a phone, scroll the graph sideways.

unseen seen on call stack appended

Dependency-first output being built

empty

A Value enters this list only after every recursive parent call has returned.

What the current structures mean

stack answers “which calls are waiting?” · seen prevents scheduling one shared Value twice · safe_order is the list we will reverse.

enter start one call and mark new recurse to an operand skip seen immediate return for a shared Value; this exact graph never needs it append parents are finished unwind child call returned return sorting is finished reverse enter the backward schedule Keyboard when the panel itself is focused: ← previous · → next · Space play/pause · Home reset.
Dependency-first order: w → x → m → b → a → y → e → L
Reverse for backward: L → e → y → a → b → m → x → w
Each operand appears before the output that uses it; reversing makes each output ready before it sends gradient contributions to its operands.

The invariant

Wait until the gradient is complete

The forward graph points from operands to outputs. The traversal follows stored parent links in the opposite direction and appends on the way back. Reversing that list puts every output before the operands whose gradient buffers it updates.