Problem. A model is described as a list of operations, each with a name, the names of its input tensors and the size of its output tensor:
x = input 4 MB
a1 = conv(x) 20 MB (a large intermediate)
a2 = pool(a1) 2 MB
b1 = conv(x) 20 MB (another branch)
b2 = pool(b1) 2 MB
y = add(a2, b2) 2 MB
loss = mse(y) 0 MB
Return an execution order in which every op runs after the ops that produce its inputs, and the peak memory reached if each tensor is freed right after its last use. Reject graphs with a cycle.
Why it matters. This is what every deep learning runtime does before executing a graph: PyTorch's torch.compile and
torch.fx, ONNX Runtime, TensorFlow graphs, XLA. The order must respect dependencies (a topological sort), backpropagation walks
the same graph in reverse topological order, and among valid orders the runtime prefers ones with low peak memory, which is
often what decides whether a model fits on a GPU.