Lesson 2.3
Topological Order
Backprop only works if you visit nodes in the right order. A node's gradient isn't final until every place that uses it has reported back. Getting that order right is a topological sort.
Socks before shoes.
Some steps have to happen before others. You can't put shoes on before socks. Backprop has the same constraint: you can't finalize a node's gradient until every node that uses it has already sent its contribution (remember, fan-out means gradients add up, lesson 2.2). Compute a node too early and its gradient is incomplete when you use it to push further back.
The order that always works.
A topological order of the graph lists every node after the things it's built from. For our example e = (a × b) + c, one topological (forward) order is:
Backward needs the right order
a node is only done once everything that uses it has reported, socks before shoes
reverse topological order: output first, then inward
For the backward pass you walk this in reverse: e, c, d, b, a. Going in reverse guarantees that by the time you reach any node, every node that consumes it has already run and deposited its gradient. So when you process d, both its consumers (here, just e) are already done, and d.grad is complete.
How you build that order.
The standard way is a depth-first walk from the output: visit a node, recurse into the nodes that produced it, and add the node to a list after its producers are added. That yields the forward topological order; reverse it for backprop. (A "visited" set keeps you from doing a node twice when paths merge.)
Put the last three lessons together and the whole algorithm fits in one sentence: backward() = topologically sort the graph, seed the output gradient at 1, then walk the nodes in reverse, each one pushing its local gradient onto its inputs and accumulating. That sentence is the engine. Everything you'll write is a faithful transcription of it.
Key takeaways
A node's gradient is only complete after all its consumers have contributed, so order matters.
Build a topological order (depth-first from the output), then walk it in reverse for the backward pass.
backward() = topological sort + seed 1 + reverse walk applying local gradients and accumulating.