Bridges: DSA to LLMs

Matrix multiplication: the shared engine

The same operation running ML and attention

~10 minLesson 34 of 57Written by Claude Opus 4.8

Here is the punchline of the whole course. One operation - matrix multiplication, built out of nothing but dot products - is the engine underneath both tracks you have been learning. Counting paths in a graph, filling a dynamic-programming table, and every single sublayer of a Transformer ( $Q K^{⊤}$ attention scores, softmax·V, the feed-forward MLPs) are all the same computation with different numbers poured in. Once you feel that in your fingers, the two fields stop being two fields.

The one-line idea

A matrix product asks one question, over and over: how much does row $i$ line up with column $j$ ? That "line up" is a dot product - a sum of products. In a graph it counts shared middle-nodes (two-hop routes). In attention it measures query-key similarity. Same question, same machine.

One recipe: rows dotted with columns

The dot product of two length- $n$ vectors is a single number - multiply component-wise, then add. Matrix multiplication is just that dot product run once for every (row, column) pair of the two inputs:

u \cdot v = k = 1 \sum n u_{k} v_{k}, C_{ij} = k = 1 \sum n A_{ik} B_{k j} = (row i of A) \cdot (col j of B) .

That single formula is the whole show. Its cost is easy to read off: to fill an $m \times k$ output you compute $m \cdot k$ dot products, and each one is a sum of $n$ multiply-adds. So multiplying an $(m \times n)$ matrix by an $(n \times k)$ matrix takes

(m \times n) (n \times k) ⟶ (m \times k), cost = O (m \cdot n \cdot k) .

Nothing here knows or cares whether the numbers came from a graph or a neural net. That indifference is exactly why it can be the shared engine. Let's prove it - by running the identical animation on two problems that look nothing alike.

The same computation, twice

Below, one stepper drives two panels. On the left we square a graph's adjacency matrix, $A \cdot A = A^{2}$ , whose entries count 2-hop paths between nodes - the graph idea from Graphs, BFS, and DFS. On the right we multiply queries by keys, $Q \cdot K^{⊤}$ , whose entries are the raw attention scores from Self-attention: query, key, value. Watch the same cell $(i, j)$ light up in both, filled by the same term-by-term dot product. The arithmetic is byte-for-byte identical.

The same matmul, twice step the shared dot product

Graph: A² = 2-hop path counts

A - rows

A - cols

A² - 2-hops

Σ = 0A²(1,1) = 0·0 + 1·1 + 1·1

Attention: QK^T = raw scorestokens: the · cat · sat

Q - queries

K^T - keys

S - scores

Σ = 0S(1,1) = 3·2 + 0·1 + 1·0

Cell (1, 1): both panels dot row 1 with column 1 - the very same operation, one product at a time.

One stepper, two meanings, identical arithmetic. Row i of the left factor is dotted with column j of the right factor - nine cells, three multiply-adds each - in both panels at once.

The aha: it was never two operations

Read off the finished grids. On the left, $A^{2}$ has a 2 on every diagonal - each node has two 2-step walks back to itself (out to a neighbour and back). On the right, $S = Q K^{⊤}$ has a 6 on every diagonal - each token's query best matches its own key, so it attends most to itself. Different story, but you got both numbers from the exact same nested sum $\sum_{k} A_{ik} A_{k j}$ versus $\sum_{k} Q_{ik} (K^{⊤})_{k j}$ . Change the matrices, keep the kernel: that is the entire trick.

Why this is the whole game

Attention does not stop at $Q K^{⊤}$ . The scores are scaled and squashed into weights, which then blend the value vectors - three matmuls back to back:

Attention (Q, K, V) = softmax (\frac{Q K ^{⊤}}{d _{k}}) V .

And the projections that make $Q$ , $K$ , $V$ are themselves matmuls: a weight matrix is a linear map, $y = W x$ , that sends every input vector to a new space. The feed-forward block in each layer? Two more weight matrices with a nonlinearity between them. Stack a hundred of these and a language model is, almost literally, matrix multiplication all the way down. This is also why GPUs exist in the shape they do: their tensor cores are thousands of multiply-add units wired to chew through GEMM (general matrix multiply, the level-3 BLAS routine). Make your problem a matmul and the hardware is already built for it - one more reason both graph analytics and deep learning ended up on the same silicon.

import numpy as np

# LEFT - graph: 2-hop path counts are the adjacency matrix squared
A = np.array([[0,1,1], [1,0,1], [1,1,0]])   # triangle on nodes 1,2,3
two_hop = A @ A                              # -> [[2,1,1],[1,2,1],[1,1,2]]

# RIGHT - attention: raw scores are queries times keys-transposed
Q = np.array([[3,0,1], [1,3,0], [0,1,3]])    # one query row per token
K = np.array([[2,1,0], [0,2,1], [1,0,2]])    # one key row per token
scores  = Q @ K.T                            # -> [[6,1,5],[5,6,1],[1,5,6]]

# same operator, same GPU kernel:  @  ==  np.matmul  ==  a GEMM

Two problems, one operator

Check yourself

Multiplying an m×n matrix by an n×k matrix costs on the order of:

The graph 2-hop count (A²)ᵢⱼ and the attention score (QK^T)ᵢⱼ are produced by:

Recall: what single operation computes both graph 2-hop path counts and attention scores, what is one entry of it, and what does it cost?

Nail down the shared engine. Try to state it, then check.

Lock it in

Matrix multiplication is a grid of dot products - row $i$ of the left factor dotted with column $j$ of the right factor, for every $(i, j)$ pair.
Squaring a graph adjacency matrix ( $A^{2}$ ) and computing raw attention scores ( $Q K^{⊤}$ ) are the same operation with different numbers poured in.
Cost is $O (m \cdot n \cdot k)$ for an $(m \times n) (n \times k)$ product - the GEMM that GPUs are physically optimized to execute.
Every sublayer of a Transformer (projections, attention scores, value blend, feed-forward) is a matmul - the single kernel underneath both fields.

Primary source

For the geometric intuition that a matrix product is a composition of linear maps, watch 3Blue1Brown's Essence of Linear Algebra (the matrix-multiplication chapters). For the same operation dressed as attention - $Q K^{⊤}$ scores, softmax, and the value blend - read Jay Alammar's The Illustrated Transformer, the clearest visual walk-through of a Transformer's matmuls anywhere.

Ask your teacher

This is the moment the two tracks fuse. Attention scores ( $Q K^{⊤}$ ) and graph 2-hop counts ( $A^{2}$ ) are the same matmul from Matrices and matrix multiplication - you just watched one stepper compute both. Learn matrix multiplication once and you have understood the core arithmetic of both fields. Ask me why attention divides by $d_{k}$ , how $A^{ℓ}$ counts length- $ℓ$ paths, or how the naive $O (n^{3})$ matmul gets beaten by Strassen's algorithm and by GPU tiling.