Matmul Forward and Backward With Broadcast Batches
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
aandbare at least 2-D, with at most 3 batch dimensions; all sizes are at most 5.grad_outhas the broadcast shape ofa @ 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 2Show 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
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium