Does it make sense to cache the result of topological sort?

[sayanb]

Every time backward() is called, it performs a topological sort. On a very large network with multiple backward passes, this could be computationally very expensive. Does it make sense to cache the result of the topological sort just once and use it every subsequent time, since the structure of the network does not change between multiple forward and backward passes?

[s-adhit]

well from what I understand from karpathy's video for every forward pass the graph is rebuilt because the value is changing, hence the backward pass should always create a new topological order since the graph structure is different

[burlachenkok]

Hello,

We built BurTorch (https://arxiv.org/pdf/2503.13795, https://github.com/burlachenkok/burtorch), which outperforms many systems on small computational graphs and micrograd was our inspiration.

It provides flexibility in how topological sorting is handled, although the implementation is quite subtle.

From an algorithmic perspective, this is a nice property. As with DFS, the complexity of topological sorting is
O(V+E). However, the real challenge lies in implementing it efficiently. In BurTorch, we emulate stack-based function calls to make the execution faster.

The idea is subtle. Due to space limitations, we did not describe it in detail in the paper.

In the code, leaf nodes and intermediate nodes are placed into two separate sets.

Most likely, the leaf nodes will differ (for example, when embeddings change). However, it is often the case that the internal nodes remain the same if only the leaf nodes are changing.

So it is possible a lot of times, but it is subtle.

[SAHAYAASHIKLIBU]

@sayanb It fails in many sequence-modeling tasks because sequence lengths can vary between inputs.