MLSYS ENGINEERING

11.3. Computation graph

To optimize a sequence of operations, the compiler must first capture it. The compiler does this through tracing: it runs the Python code and records each operation along with the tensors that flow between them. The resulting data structure is called a computation graph.

The following figure illustrates the computation graph for x @ w + b.

x w @ z b + y
Figure 54. Computation graph for x @ w + b.

In the figure above, the circles represent tensors, while arrows pointing to the same output tensor represent an operation. The arrows from x and w converge at z to represent the matrix multiplication, producing the intermediate tensor z. The arrows from z and b then converge at y to represent the addition, producing the final output tensor y.

How does an ML compiler capture this in Python? Instead of running real data through the model, it runs the code with symbolic tensors, as defined in the following code.

Code 30. A symbolic tensor class.
ops = []

class SymbolicTensor:
    def __init__(self, name):
        self.name = name

    def __matmul__(self, other):
        out = SymbolicTensor("z")
        ops.append(([self.name, other.name], "@", out.name))
        return out

    def __add__(self, other):
        ...

As you can see, the symbolic tensor does not have actual values; it only has a name. In real implementations like PyTorch, a symbolic tensor also tracks metadata such as its shape and data type (dtype), which the compiler needs to optimize execution. While our example overrides Python operators directly, modern systems such as PyTorch's TorchDynamo analyze Python bytecode to intercept operations. Regardless of the implementation, the core purpose is the same: capturing the graph of operations without evaluating concrete numbers.

Next, we define our function and run it with symbolic tensor inputs to trace the execution.

Code 31. Tracing the linear layer with symbolic inputs.
def linear_layer(x, w, b):
    return x @ w + b

x = SymbolicTensor("x")
w = SymbolicTensor("w")
b = SymbolicTensor("b")

output = linear_layer(x, w, b)

During execution, each operation appends its inputs, operator symbol, and output to the global ops list. We can print the captured operations to see the recorded graph.

Code 32. Printing the captured operations.
for inputs, op, out in ops:
    print(inputs, op, out)
# ['x', 'w'] @ z
# ['z', 'b'] + y

Now that we have the inputs and outputs of each operation, we can easily reconstruct the entire computation graph. By matching the output of one operation to the inputs of another, the compiler connects individual operations into a complete graph.

In this example, we only traced two simple operations, x @ w + b. In practice, an ML compiler can trace much larger workloads. You can trace an entire model or even the whole training step, combining the forward pass, loss calculation, backward pass, and optimizer updates into a single computation graph. Seeing the entire training step all at once gives the compiler a big-picture view, allowing it to find optimizations that are impossible when running each step separately.