Matmul Forward and Backward With Broadcast Batches

HardML Coding

Reported in interviews at OpenAI

Problem statement

You are writing a custom matrix-multiply op for a small autograd library (the kind of thing you would wrap in a torch.autograd.Function). The forward pass computes $C = AB$; the backward pass receives the upstream gradient $dC = \partial L / \partial C$ and must return $\partial L / \partial A$ and $\partial L / \partial B$.

The op must follow np.matmul semantics: a has shape [..., m, k], b has shape [..., k, n], and the leading batch dimensions broadcast. That covers the plain 2-D case, a batch of inputs times one shared weight matrix, and batch dimensions of size 1 on either side. Each returned gradient must have exactly the shape of its input.

Implement it in numpy and return the forward result together with both gradients:

def matmul_forward_backward(a: list, b: list, grad_out: list) -> list:
    # returns [C, grad_a, grad_b] as nested lists of floats
    ...

Be ready to derive the gradients at the index level, not just quote the matrix formulas. As a follow-up, the interviewer may ask how a parallel prefix scan (Hillis-Steele) could parallelize the accumulation over the contraction dimension in a tiled version, and when that is or is not the right tool.

Constraints

  • a and b are at least 2-D, with at most 3 batch dimensions; all sizes are at most 5.
  • grad_out has the broadcast shape of a @ b. Answers are compared with a relative tolerance of $10^{-6}$.

Example 1 (plain 2-D)

a = [[1, 2, 3], [4, 5, 6]]            # 2 x 3
b = [[1, 0], [0, 1], [1, 1]]          # 3 x 2
grad_out = [[1, 0], [0, 1]]
-> C      = [[4, 5], [10, 11]]
   grad_a = [[1, 0, 1], [0, 1, 1]]
   grad_b = [[1, 4], [2, 5], [3, 6]]

Example 2 (a batch of 2 inputs times one shared weight)

a = [[[1, 0, 2], [0, 1, 0]],
     [[2, 1, 0], [1, 1, 1]]]          # 2 x 2 x 3
b = [[1, 2], [0, 1], [1, 0]]          # 3 x 2, shared across the batch
grad_out = [[[1, 1], [0, 1]], [[1, 0], [2, 1]]]
-> grad_b = [[5, 2], [3, 2], [4, 3]]  # shape 3 x 2, summed over the batch

Example 3 (size-1 batch dimension on a)

a: shape 1 x 2 x 2 = [[[1, 2], [3, 4]]]
b: shape 3 x 2 x 1 = [[[1], [0]], [[0], [1]], [[1], [1]]]
grad_out: shape 3 x 2 x 1 = [[[1], [1]], [[1], [0]], [[0], [2]]]
-> C      = [[[1], [3]], [[2], [4]], [[3], [7]]]
   grad_a = [[[1, 1], [3, 2]]]        # stays 1 x 2 x 2
Show hint

Start from one scalar entry of $C$ and ask which entries of $C$ a single entry of $A$ influences.

Relevant roles: ML Engineer, Deep Learning Engineer, Research Scientist and AI Engineer.

Related free problems