Bridges: DSA to LLMs

Graphs and adjacency matrices to attention

How graph structure becomes attention weights

~11 minLesson 39 of 57Written by Claude Opus 4.8

In Graphs, BFS, and DFS you learned that a graph is just things and the connections between them, stored as an $n \times n$ adjacency matrix. In The attention mechanism you learned that attention builds an $n \times n$ grid of weights saying how strongly each token looks at every other. Those are the same object. An attention layer takes your sentence, treats every token as a node in a fully-connected graph, and writes a directed, weighted edge from each token to each token. Softmax just makes each node's outgoing edges sum to 1. Once you see it, transformers stop being magic and become a familiar data structure with a training loop.

The one-line idea

Take a sentence. Draw a node for every token. Draw a directed edge from token $i$ to token $j$ whose thickness is how much $i$ attends to $j$ . Collect those thicknesses into a matrix and you have the attention matrix - which is exactly the weighted adjacency matrix of that token graph. Attention is a graph you compute on the fly.

Recall: nodes, edges, and the adjacency matrix

A graph is a set of nodes joined by edges. Edges can be directed (a one-way arrow $i \to j$ ) and can carry a weight (a number on the edge). The adjacency matrix $A$ stores all of it: $A_{ij}$ is the weight of the edge from node $i$ to node $j$ , or $0$ when there is no edge. For an unweighted graph the entries are just $1$ and $0$ ; swap the $1$ s for weights and you have a weighted adjacency matrix. Row $i$ lists everything node $i$ points at.

The attention matrix is a weighted adjacency matrix

Here is the whole translation, term for term. Nothing on the right is a metaphor - each row is a literal identity.

Graph	Attention
node / vertex $i$	token (position) $i$
directed edge $i \to j$	token $i$ attends to token $j$
edge weight $A_{ij}$	attention weight $α_{ij}$
adjacency matrix $A$	the $n \times n$ attention matrix
neighbor aggregation	the blend $\sum_{j} α_{ij} v_{j}$
fully-connected graph	every token attends to every token

Formally, the attention weights are the adjacency entries:

A_{ij} = α_{ij} = softmax_{j} (\frac{q _{i} \cdot k _{j}}{d}), j = 1 \sum n A_{ij} = 1.

Two things make this a special kind of adjacency matrix. It is weighted and directed - $A_{ij} \neq = A_{j i}$ in general, because "the" leaning on "cat" is not the same as "cat" leaning on "the." And it is row-stochastic: softmax forces every node's outgoing edges to sum to $1$ , so each token spreads exactly one unit of attention across the graph. Play with the two views below - they are the same numbers drawn two ways.

One matrix, two views drag temperature - toggle the mask

Left: the token graph - each arrow is a directed edge, thicker = more attention. Right: the same weights as an adjacency heatmap (row i -> column j). Click a node or a row to focus it; the two views stay locked together.

Attention temperature T1.00

Adjacency / attention matrix

qk ->

the1

cat2

saw3

the4

bird5

row saw: the 0% - cat 26% - saw 3% - the 0% - bird 70% - Sum 100%

saw (pos 3) sends most of its edge weight to bird (70%), then cat (26%).

The amber dashed ring on the focused node is its self-loop - how much the token attends to itself (the matrix diagonal). Edges bowing up point to later tokens; edges bowing down point to earlier ones.

The aha: temperature is an edge-pruning dial

Slide $T$ down and watch the focused node's four edges collapse toward a single thick arrow - the heatmap row lights up one bright cell. Slide $T$ up and the edges even out into a uniform web - the row turns evenly grey. Same graph, same nodes; the temperature just decides how sharply the attention (edge weight) concentrates. Sharpening attention is literally sparsifying a graph.

Fully-connected, masked, sparse - it's all about which edges exist

Plain self-attention is a complete graph: every token has an edge to every token, $n^{2}$ of them - which is why attention costs $O (n^{2})$ and hits the "attention wall." A decoder that generates left-to-right cannot let a token peek at the future, so it applies a causal mask: forbid every edge $i \to j$ with $j > i$ . Toggle the mask in the demo and the graph collapses - all the up-bowing "future" arrows vanish, every remaining arrow points backward, and the heatmap becomes lower-triangular.

Causal mask = a directed acyclic graph

Masking sets the forbidden scores to $- \infty$ before softmax, so their weights become $0$ :

A_{ij}^{causal} = 0 for j > i ⟹ A is lower-triangular.

Now read it as a graph. Every edge runs from a token to an earlier token (ignoring self-loops), so you can never follow arrows in a circle and return - that is the definition of a directed acyclic graph (DAG). Its topological order is simply the reading order of the sentence. The very first token has no past, so its row is forced to a single self-loop: it attends 100% to itself. And the blend a token computes,

h_{i}^{'} = j = 1 \sum n A_{ij} v_{j},

is exactly message passing on this graph - each node aggregates its neighbors' values, weighted by the edge to them. That single equation is why transformers are a special case of graph neural networks: a GNN whose graph is the complete (or causal) token graph, with edge weights recomputed by attention at every layer.

import numpy as np

# scores[i][j] = q_i . k_j / sqrt(d)  ->  raw edge strengths (n x n)
scores = Q @ K.T / np.sqrt(d)

# causal mask: a token may only reach itself and the past (j <= i)
future = np.triu(np.ones((n, n), bool), k=1)   # True strictly above the diagonal
scores[future] = -np.inf                       # forbid every future edge

A = softmax(scores, axis=1)   # weighted adjacency: each ROW sums to 1
# A[i][j] is the directed edge weight  token i -> token j

H = A @ V                          # message passing: blend neighbors by edge weight

Attention -> adjacency, in NumPy

Check yourself

In the graph view of attention, a single entry alpha_ij of the matrix is:

Applying a causal mask turns the token graph into:

Why is an attention layer literally a graph neural network running on the tokens?

Make the connection stick. Try to state it, then check.

Every token is a node; the attention weight

α_{ij}

is a directed, weighted edge

i \to j

; the full

n \times n

attention matrix is the weighted adjacency matrix of a fully-connected token graph, made row-stochastic by softmax. The output blend

h_{i}^{'} = \sum_{j} α_{ij} v_{j}

is message passing - a node aggregating neighbors weighted by their edges. A causal mask deletes future edges, turning the complete graph into a DAG.

Lock it in

The attention matrix is literally a weighted adjacency matrix: tokens are nodes, attention weights are directed edges, and each row sums to 1 (row-stochastic).
Temperature controls sparsity: low T concentrates edges on a single neighbor, high T spreads weight uniformly - sharpening attention is pruning the graph.
A causal mask removes all future edges, making the graph a DAG whose topological order is the reading order; the first token has only a self-loop.
The output blend is exactly message passing on this graph - transformers are a special case of graph neural networks with edge weights recomputed at every layer.

Primary source

For attention drawn as weighting - queries scoring keys, softmax turning scores into edge strengths - read Jay Alammar's The Illustrated Transformer. For interactive, graph-flavored explainers that let you manipulate these matrices directly, browse the collection at Distill.pub.

Ask your teacher

This is where the two paths of the course become one object seen through two lenses. BFS and DFS traverse a graph's edges; attention computes a weighted graph over tokens - same nodes-and-edges structure, different question asked of it. The link goes further into practice: GraphRAG literally runs graph traversal over a knowledge graph to retrieve the context an LLM then attends over. Ask me how sparse and local attention pick which edges to keep, why the $O (n^{2})$ complete graph is the "attention wall," or how message-passing GNNs and transformers unify formally.