Part IV · How many Gaussians? · Chapter 13

Budgets and description length

About 20 minutes. Tap Continue to move on; nothing later depends on anything you have not yet seen.

13.1 The second half of the research question

Part III asked where to put a fixed number of Gaussians. The research question has a second half: how many to use, and whether the number should follow the complexity of the scene. That number is not a detail. It decides how much the representation stores, how much it costs to compute, and how close it can get to the teacher.

This chapter gives you the tools to talk about the count precisely: as a budget, as a point on an error curve, and as a choice that information theory has a principled answer for. Chapter 14 then shows what happened when the project tried to let each image choose its own count.

By the end you can state what a Gaussian costs in stored numbers, read the project's error-against-count curve, explain why one model trained at 64 serves 16 to 256, and say what a defensible “budget curve” claim must contain.

Before reading on: if a reviewer asks “why 64 Gaussians?”, what would you answer today?

13.2 The count is a budget

Each Gaussian stores six numbers of geometry (Chapter 2: two for the centre, three for the Cholesky factor, one mass logit) and one feature vector of 384 numbers (Chapter 4). That is 390 numbers per Gaussian.

Budget. The number of Gaussians K allowed per image. It fixes the stored size (390 K numbers), the size of the least-squares system (K × K), and so the compute.

Compare with the teacher grid it replaces. On the 32×32 target (Chapter 8) the grid holds 1024 × 384 = 393,216 numbers.

Gaussians KStored numbersShare of the 32×32 grid
166,2401.6%
6424,9606.3%
25699,84025.4%

Now the trap that Chapter 8 hinted at. The old 16×16 target holds 256 × 384 = 98,304 numbers. With 256 Gaussians the representation stores more numbers (99,840) than the target it compresses, and indeed per-image k-means with 256 Gaussians fits it with an error of about 6 × 10−12, which is exact up to rounding (s6_split_hierarchy.json, 200 images). Above about 96 Gaussians the error curve on that target says nothing about placement. A budget is only meaningful when it is well below the size of the thing being represented.

Compute grows faster than storage. The least-squares solve of Chapter 4 factorises a K × K matrix, which costs on the order of K3; the project needed a blocked Cholesky above 128 Gaussians. Chapter 18 covers how.

13.3 Error against count

The first thing to know about any budget is how the error falls as it grows. The project measured this on the 32×32 input512 target (quick experiment s7, plain PyTorch, first 100 holdout images, clustering width tuned on the same images):

Kk-means + 16 Adam stepsPer-image optimum (200 steps)Error ratio per doubling (optimum)
160.0003390.000315–
320.0002070.0001860.59
640.0001170.00009880.53
1280.00006520.00005040.51
2560.00003670.00002320.46

Read the last column: each doubling of the count roughly halves the error at the optimum. On log–log axes that is a straight line with slope about −1, so the error behaves roughly like c / K over this range. The count matters a great deal: the optimum at 256 is about 14 times lower than at 16.

Dense error against number of Gaussians, log-log axes, 32 by 32 input512 target 3e-4 1e-4 3e-5 16 32 64 128 256 Gaussians (each step doubles) dense MSE k-means + 16 steps (100 images): 16 Gaussians, 0.000339 k-means + 16 steps (100 images): 32 Gaussians, 0.000207 k-means + 16 steps (100 images): 64 Gaussians, 0.000117 k-means + 16 steps (100 images): 128 Gaussians, 6.52e-05 k-means + 16 steps (100 images): 256 Gaussians, 3.67e-05 k-means +16 Model J trained at 64, 16 steps (800 images): 16 Gaussians, 0.000346 Model J trained at 64, 16 steps (800 images): 32 Gaussians, 0.000207 Model J trained at 64, 16 steps (800 images): 64 Gaussians, 0.000114 Model J trained at 64, 16 steps (800 images): 128 Gaussians, 6.42e-05 Model J trained at 64, 16 steps (800 images): 256 Gaussians, 3.74e-05 Model J Per-image optimum, 200 steps (100 images): 16 Gaussians, 0.000315 Per-image optimum, 200 steps (100 images): 32 Gaussians, 0.000186 Per-image optimum, 200 steps (100 images): 64 Gaussians, 9.88e-05 Per-image optimum, 200 steps (100 images): 128 Gaussians, 5.04e-05 Per-image optimum, 200 steps (100 images): 256 Gaussians, 2.32e-05 optimum

The figure plots the table and, in colour, the trained model of the next step. Tap or hover a point for its value. The k-means and optimum curves use 100 images; the model uses all 800 holdout images, one seed.

Notice too that the gap between “k-means + 16 steps” and the optimum widens with K: 8% at 16, 58% at 256. With more Gaussians there is more to place, and 16 steps of refinement get less of the way there.

13.4 One model, many budgets

Must you train a separate model for each count? A neat idea from representation learning says no, if you train for it.

Ordered (nested) representation. A representation in which the first m parts are themselves a good representation at budget m, for many values of m. One model then serves many budgets by truncation.

Nested dropout trains this ordering by randomly truncating the latent units during training, so the early units learn to carry the most important information[Rippel et al., 2014]. Matryoshka representation learning applies the same principle to embeddings: one vector whose prefixes are each usable, trained with a loss at several prefix lengths[Kusupati et al., 2022].

This project got a version of that property without training for it. Model J was trained at 64 Gaussians on input512, yet evaluated at other counts with no retraining it gives (all 800 holdout images, one seed, artifacts/any-count-20261120/step1.json):

K16 steps32 steps32 steps over the optimum (100 images)
160.0003460.000332+3%
320.0002070.000196+4%
640.00011370.0001062+5%
1280.00006420.0000575+12%
2560.00003740.0000307+32%

On the first 100 images, the 16-step values are within about 4% of per-image k-means + 16 steps at every count (4% better at 64, 3% worse at 256).

Why it works. Almost nothing in the model depends on the count. The starting layout is a Halton sequence, a deterministic list of points in the square built so that every prefix of the list is spread evenly; asking for 16 or 256 points just takes a shorter or longer prefix, which is the nested property by construction. The other count-dependent part, one learned query per slot, matters little: new slots borrow the query of the trained slot whose starting centre is nearest (evaluate_fine_any_count_20261120.py). The clustering and refinement stages of Chapters 10 and 11 operate on whatever set they are given.

Does training at the count close the gap? The gap to the optimum grows with count (32% at 256), so the project trained model J from scratch at 16, 32, 128 and 256 Gaussians (6,000 updates each, one seed, final checkpoints, 800 holdout images, 16 steps):

KTrained at KTrained at 64, used at KDifference
160.0003380.000346−2%
320.0002050.000207−1%
1280.00007430.0000642+16%
2560.00003900.0000374+4%

Training at the count helps by 1 to 2% at small counts and loses at large ones. At 128 and 256 the holdout error was lowest after 500 to 1,500 updates (best 0.0000659 at 128, 0.0000347 at 256) and then rose while the training loss stayed flat. The roadmap's reading: training at large counts is not the lever; transfer from 64 is. The 16 and 32 numbers come from the runs' summary.json files; the 128 and 256 numbers are in the roadmap run log.

13.5 Description length: a principled price for a Gaussian

The error always falls as you add Gaussians, so “lowest error” cannot choose the count. You need a price. Minimum description length (MDL) supplies one.

Minimum description length. Choose the model that gives the shortest total code for the data: the length to describe the model, plus the length to describe the data's residual given the model[Grünwald, 2004].

A crude but standard version, in natural units (nats). If the residual is treated as independent Gaussian noise with variance equal to the mean squared error E, describing N numbers costs about

Ldata ≈ (N / 2) · ln E + constant

and describing P real parameters, each to the precision the data can support, costs about

Lmodel ≈ (P / 2) · ln N

This second line is the familiar Bayesian information criterion penalty. Put in the project's numbers: N = 393,216, P = 390 K, so each stored number costs ½ ln N ≈ 6.4 nats. Doubling from 64 to 128 at the optimum lowers Ldata by about 132,000 nats and adds 64 × 390 × 6.4 ≈ 161,000 nats of model. Not worth it. From 32 to 64 the saving (124,000) beats the cost (80,000). Under this code, 64 is the shortest description.

Try it yourself. The second slider sets how many of the 384 feature dimensions you treat as independent; real features are strongly correlated, so the effective number is smaller.

KData, vs 16ModelTotal, vs best

How to use this in a talk. It is an illustration, not a result. The independent-noise assumption is false, the price per parameter is a convention, and the curve is the per-image optimum on 100 images. Its value is the framing: the count is a trade between the cost of describing Gaussians and the cost of describing what they miss, and with a stated price the trade has an answer. Lower the price and the answer moves to 256; that sensitivity is the honest caveat.

Go deeper: the information bottleneck

A related framing asks for the most compressed description of an input that still keeps what matters about a relevant variable[Tishby et al., 2000]. Here the “relevant variable” would be the teacher field and the compression the Gaussian budget. It gives vocabulary, not a stopping rule you can compute directly from the project's numbers.

13.6 Letting each image choose: halting and splitting

MDL picks one count for a whole dataset. The research question wants more: a count that follows each image's complexity. Two families of ideas lead there.

Adaptive computation. Adaptive Computation Time lets a recurrent network decide how many steps to spend on each input, with a learned halting signal and a “ponder cost” that charges for every extra step[Graves, 2016]. PonderNet recasts halting as a probability per step with a prior over the number of steps, which gives lower-variance training[Banino et al., 2021]. Read “steps” as “Gaussians” and the ponder cost as the price per Gaussian, and you have a per-image budget.

Growing by splitting. Start small and repeatedly divide the Gaussian whose division helps most, until a stopping rule says stop. Two kinds of score were candidates:

  • Error-based: split where the least-squares residual (Chapter 4) is largest inside the Gaussian's region.
  • Information-based: assign every teacher token to its nearest prototype in a small codebook (256 prototypes from k-means on training features). A Gaussian whose region mixes many prototypes has high code entropy. Its information gain is that entropy in the parent minus the entropy in its two would-be children: how much a split would separate different kinds of content.
Information gain (of a split). Entropy of the prototype codes owned by the parent, minus the responsibility-weighted entropy of the codes owned by the two children. High gain means the split separates different content.

An MDL stopping rule closes the loop: split while the drop in Ldata exceeds the price of one more Gaussian. On paper this is exactly the hierarchical, complexity-following placement the research question asked for. Chapter 14 shows what the measurements said.

13.7 What a budget-curve claim needs

A “budget curve” is a claim of the form: at every count, this method reaches this error or accuracy, and that is better than the alternatives at the same count. To defend one, you need each of these.

  1. The same model at every point, or say otherwise. State whether each count is a separate model or one model; the one-model case is the stronger claim, and the per-count runs test what it costs.
  2. Baselines at equal budget. At least average pooling of the grid and per-image k-means with the same number of tokens. Chapter 16 adds the token-merging and adaptive-patch baselines from the literature.
  3. An honest x-axis. Count alone hides that a Gaussian stores 390 numbers and a pooled token 384. Report stored numbers too.
  4. A target that does not saturate. The 16×16 grid is fitted exactly at 256 Gaussians, so curves on it are meaningless past about 96.
  5. The ceiling at each count. The per-image optimum shows how much of the remaining error is placement and how much is the budget itself.
  6. A downstream axis. Error against the teacher is the project's metric; a reviewer will want task accuracy against count as well (roadmap P1).
  7. Rigour. Several seeds, the same images for every curve, and a test set that no setting was tuned on. Chapter 19 covers this.

Today the project has items 1 (one model, compared with per-count models), 4 and 5 on one seed, partial 2 (k-means, on 100 images), and not 6 or the sealed set in 7.

13.8 Check yourself

Answer from memory; each question gives its reason once you choose.

1. Why is the error curve on the 16×16 target meaningless above about 96 Gaussians?

256 Gaussians store 99,840 numbers against the target's 98,304 and fit it to about 6e-12. Once the budget approaches the target's size, low error says nothing about placement.

2. Why can a model trained at 64 Gaussians run at 256?

Nothing in the model depends on the count except the Halton start layout, whose every prefix is evenly spread, and per-slot queries, which matter little. Random-count training was built but not launched.

3. In the description-length view, what stops you adding Gaussians forever?

The error keeps falling (it roughly halves per doubling). The model term grows with every stored number, so a Gaussian is worth adding only if it shortens the residual code by more than it costs.

4. A reviewer says the BIC calculation “proves 64 is optimal”. Your best reply?

The code assumes independent Gaussian residuals and a conventional price per parameter; lowering the price moves the answer to 256. It frames the trade, it does not settle it.

5. What does information gain measure for a candidate split?

Information gain is about how mixed the content is under the Gaussian, measured with codebook entropy. It does not look at the reconstruction error, which is the gap Chapter 14 exposes.

13.9 Close the loop

Answer the reviewer again: “Why 64 Gaussians, and could you use another number?” Use the words budget, error curve and description length. Then compare with your first answer.

A model answer

“The count is a budget: 64 Gaussians store about 6% of the 32×32 teacher grid. Error roughly halves with each doubling of the count, so there is no natural stopping point from error alone; under a simple description-length code, the saving from going past 64 no longer pays for the extra parameters, though that depends on the price per parameter. 64 is a working point, not a claim. The model trained at 64 runs at any count from 16 to 256 without retraining, within about 4% of per-image k-means with the same refinement, and we report the whole curve, with the gap to the per-image optimum growing to 32% at 256. Models trained separately at each count do not close it: 1 to 2% better at 16 and 32, worse at 128 and 256, one seed.”

Read next Kusupati et al., “Matryoshka Representation Learning” (2022), the introduction and method. The cleanest statement of “one model, many budgets”, and the training recipe you would cite if the per-count runs show that training for several counts helps.

Something unclear, or want to rehearse how you would say this to a reviewer? Ask your teacher in the chat.

One-page summary of this chapter ·