9.1 Placement is a grouping problem
Part I gave you the read-out: given where the Gaussians are, their features follow by least squares. Part II gave you the target: a grid of DINOv3 tokens. What is left is the hardest part, and the part a reviewer will press on: where do the Gaussians go?
The classical answer is clustering. Put tokens that look alike into the same group, then let one Gaussian own each group. This chapter teaches the two classical clustering algorithms, k-means and EM, and shows exactly how your project used them: as the baseline the first trained predictor lost to, and as the starting point for per-image optimisation.
Before reading on: you have 256 tokens, each with a 384-number feature vector and a position. How would you choose where 64 Gaussians go? One or two sentences.
9.2 k-means and Lloyd's algorithm
Take P points t1, …, tP (here, the 256 token feature vectors of one image) and a number of groups K. Each group k gets a centre μk, and each point a label c(p) saying which group it is in.
Minimising J exactly is hard, because there are astronomically many labellings. Lloyd's algorithm[Lloyd, 1982] alternates two easy steps instead:
- Assign. Hold the centres fixed; give each point the label of its nearest centre. This is the best labelling for those centres.
- Update. Hold the labels fixed; move each centre to the mean of its points. The mean is the point that minimises the summed squared distance to a group, so this is the best centre for those labels.
Each step can only lower J or leave it unchanged, and there are finitely many labellings, so the algorithm stops. But it stops at a local minimum: where it ends depends on where the centres start. That is why seeding matters; k-means++ picks starting centres spread out in proportion to squared distance and comes with a guarantee on the expected result[Arthur and Vassilvitskii, 2007]. Your per-image k-means baselines use this seeding (scripts/research/quick/s3_static_layouts.py, 30 Lloyd iterations).
9.3 Soft k-means
The assign step makes a hard choice: a point halfway between two centres goes wholly to one. Small moves of a centre can flip labels, so J jumps. A softer rule lets each point share itself among the groups, more to the closer ones:
rpk = exp(−β ‖tp − μk‖²) / Σj exp(−β ‖tp − μj‖²)Here rpk is the share of point p given to group k; the shares of each point sum to one. The update step becomes a weighted mean, μk = Σp rpk tp / Σp rpk.
The number β is a stiffness. Small β: every point is shared almost equally and all centres drift to the overall mean. Large β: the nearest centre takes nearly everything, and you are back to hard k-means. In between, the assignments vary smoothly with the centres, which is exactly what a method trained by gradients will need in Chapter 10.
You have seen this formula before. It is a softmax over groups, the same shape as Chapter 3's responsibilities: rk(x) = softmax over k of (log mass + log density). The next step makes the link exact.
9.4 Gaussian mixtures and EM
Chapter 3 introduced a mixture model: K Gaussians, each with a mass πk, a centre μk and a covariance Σk, and the responsibility of each Gaussian for a point. Fitting a mixture to data means choosing those parameters so that the data are as probable as possible. The standard method is EM[Dempster et al., 1977], which has the same two-step rhythm as Lloyd's algorithm:
E-step: responsibilities, exactly as in Chapter 3: rpk = πk 𝒩(xp | μk, Σk) / Σj πj 𝒩(xp | μj, Σj) M-step: with Nk = Σp rpk, the weighted moments: πk = Nk / P, μk = Σp rpk xp / Nk,
Σk = Σp rpk (xp − μk)(xp − μk)ᵀ / Nk
In words: the mass is the share of points a Gaussian owns, the centre is the weighted mean of their positions, and the covariance is their weighted spread. Each EM round never lowers the likelihood. Bishop shows that k-means is the limit of EM when every covariance is the same small multiple of the identity and that multiple shrinks to zero: responsibilities become hard, and only the centres remain[Bishop, 2006, ch. 9].
Try both below. Each tap is one half-step. Watch the k-means objective fall and stop; then switch to EM and watch the ellipses take the shape of the long group on the right, which k-means cannot describe. Tap New start twice to reach “two centres in one group”: k-means stops at an objective of about 56.8, against about 15.6 from the other starts. That is a local minimum.
9.5 What gets clustered here: features and position
Each of your tokens has two kinds of coordinates: a 384-number feature vector tp (unit length) and a position xp in [−1, 1]². Clustering on features alone groups tokens that look alike wherever they are. Clustering with position as well, using the distance
‖tp − μk‖² + m² ‖xp − νk‖²where νk is the group's mean position and m sets the weight of position, keeps groups spatially compact. This is the idea behind SLIC superpixels, which run k-means on colour plus pixel position[Achanta et al., 2012].
Why does this matter for Gaussians? A Gaussian covers one connected, roughly elliptical region. A feature-only group can be scattered across the image (all the sky patches, left and right of a tree), and no single Gaussian can own a scattered group. Position keeps groups the shape a Gaussian can take. To turn each group into a Gaussian, the project used the M-step of 9.4 on positions: centre from the group's mean position, covariance from its spread (plus a small floor for the patch's own extent), mass from its share of tokens, then features by least squares.
Measured on the 800 holdout images at 64 groups (quick experiment, plain PyTorch, s3_static_layouts.json):
| Position weight m | Hard groups, group-mean features | Gaussians fitted to groups, least squares |
|---|---|---|
| 0 (features only) | 0.0000857 | not built (groups scattered) |
| 0.5 | 0.0000881 | 0.0000862 (best width) |
| 1 | 0.0000950 | 0.0000876 |
| 2 | 0.000111 | 0.0000964 |
A little position costs almost nothing and makes the groups usable as Gaussians; too much position forces groups to be round blobs regardless of content. The width scale was tuned on the same images, so treat the best entry as optimistic.
9.6 Why k-means is a strong baseline for dense error
Here is the fact that explains the table. Suppose the responsibilities are hard: each token belongs wholly to one group, so the matrix A of Chapter 3 has a single 1 in each row. Then the least-squares features of Chapter 4 are just the group means (ignoring the small ridge term), and the dense squared error ‖A Z − T‖² is exactly the k-means objective J on the features. Dividing by the 256 × 384 entries gives the dense MSE.
So feature k-means directly minimises the hard-assignment version of your metric. The “hard groups” column above is that number: 0.0000857. Soft, overlapping Gaussians with least-squares features can do better than hard groups, because overlaps blend neighbouring features into smooth transitions; but only if they are placed well.
This is why per-image k-means was the decisive diagnostic in the roadmap (phase 2b). At 64 Gaussians on the 16×16 target:
| Layout | Dense MSE |
|---|---|
| Static 8×8 grid, wide Gaussians | 0.000134 |
| Trained one-shot predictor (Gridless64, least squares) | 0.000104 |
| Per-image k-means, Gaussians fitted to groups | 0.000086 |
| Per-image optimisation of the Gaussians (100 images) | 0.000047 |
The trained network lost to a 30-iteration clustering of each image. And entropy-driven layouts did no better than the grid (0.000136 against 0.000134). The roadmap's decision followed: build feature-similarity clustering into the predictor. Chapter 10 covers how.
9.7 Per-image k-means as a starting point, and e-means
k-means is also where per-image optimisation starts. In quick check s5 (plain PyTorch, first 100 holdout images, least squares inside the loop), gradient-based optimisation of the Gaussians' geometry (with Adam, a standard optimiser that Chapter 11 explains), started from the k-means layout at 0.0000880, reached 0.0000729 after 4 steps, 0.0000674 after 8, 0.0000606 after 16 and 0.0000483 after 200. In the 32×32 budget study (s7) every count has a “k-means”, “k-means + 16 steps” and “k-means + 200 steps” curve; Chapter 13 reads them.
A good start matters because the problem has local minima, just like k-means itself: the same 600-step optimisation ends at 0.0000465 from a grid start and at 0.0000558 from the Gridless64 layout (100 images, s4_partial_*_ls_n100.json).
A reviewer may mention e-means, a November 2026 variant of k-means. It replaces Lloyd's full passes with mini-batch updates averaged by an exponential moving average, gives scaling laws for the decay rate and batch size, reaches Lloyd's 25-epoch loss in 1.4 to 2.6 epochs, and partitions 10 billion DINO embeddings into 16 million clusters in 2.5 epochs[Bessa et al., 2026].
It does not change this project, for two reasons. First, the scale is opposite: you solve many tiny problems (256 points, 64 groups, per image), each of which fits in one batch, while e-means targets one enormous problem. Second, and more important, speed was never the bottleneck. The bottleneck is that k-means minimises the hard objective, not the true soft least-squares error, and runs per image instead of in one forward pass. A faster k-means is still k-means.
Go deeper: why EM's likelihood never falls
EM maximises a lower bound on the log-likelihood. The E-step makes the bound touch the likelihood at the current parameters; the M-step maximises the bound over the parameters. The likelihood at the new parameters is at least the bound, which is at least the old likelihood. Bishop chapter 9.4 gives the derivation in two pages.
9.8 Check yourself
Answer from memory; each question gives its reason once you choose.
1. Why is per-image feature k-means a strong baseline for dense MSE?
2. What does EM's M-step do for one Gaussian?
3. In which limit does EM become k-means?
4. Why add position to the clustering distance?
5. A reviewer says: “Use e-means, it is ten times faster.” Your best answer?
9.9 Close the loop
Without scrolling up: explain to a reviewer why per-image k-means beat your first trained predictor, and what that told you to build next. Then compare with your first answer.
A model answer
“With hard assignments, least-squares features are group means and the dense error is exactly the k-means objective, so feature k-means directly optimises a restricted version of our metric. Adding a little position keeps groups compact, so a Gaussian fitted to each group by EM's moment step keeps the gain: 0.000086 against 0.000104 for the trained one-shot predictor. That said the predictor, not the representation, was the bottleneck, and that grouping by feature similarity is what it lacked. So we built clustering into the network. A faster k-means such as e-means would not help, because the limit is the hard objective and the per-image loop, not speed.”
Something unclear, or want to rehearse how you would say this to a reviewer? Ask your teacher in the chat.