Cost models and searching the mapspace

Because for a perfectly nested affine loop, the number of times a tensor is accessed at a level is a counting problem over the iteration space, and the counting has a formula.

The mechanism. Fix a level $\ell$ with tile factors $(T_1, \dots, T_d)$ for the $d$ loops. A tensor $X$ is indexed by an affine function of a subset $S_X$ of the loop variables. Then:

• The tile footprint of $X$ at level $\ell$ is the product of the tile extents over the dimensions $X$ actually depends on. A weight tensor indexed by $(k, n)$ has footprint $T_k \cdot T_n$, and is completely invariant to $T_m$.
• The number of times that tile is fetched is the product of the extents of the loops above level $\ell$ that $X$ does not depend on. A tensor invariant to the outer $m$ loop is fetched once and reused $M$ times; a tensor that varies with $m$ is fetched $M$ times.
• Traffic is footprint × fetch count, summed over tensors. Everything follows from which loop variables appear in which index expression.

That last bullet is the whole trick, and it is why the permutation decision from Module 5 falls directly out of the arithmetic: which loops sit above the level determines which tensors are invariant, which determines which are re-fetched. Reuse is not something you measure, it is something you read off the index expressions.

Why it is exact, and where exactness ends. The counting is exact for perfectly nested loops with affine indices, static bounds, and no data-dependent control flow — because under those conditions the access sequence is fully determined by the loop structure. This is the same property that makes the polyhedral model work, and the same property that makes compiler-managed scratchpads viable (Module 3). ML’s dense kernels satisfy it almost perfectly, which is why the whole approach works here and would not work for, say, a graph algorithm.

It ends precisely where Part Q begins. Data-dependent indices (gather, embedding lookup, unstructured sparsity) make the footprint a random variable rather than a product. Dynamic shapes make the bounds symbolic. MoE routing makes the extents themselves depend on the data. In every one of those cases the closed form is replaced by an expectation with a variance the model does not report, and the mapping chosen from an expectation can be badly wrong for the realised value. That is the deep reason Part Q is hard: not that irregular workloads are slow, but that the entire apparatus for reasoning about them stops returning a number.

Because every omitted effect is a mechanism by which reality falls short of an idealisation, and there is no corresponding mechanism by which reality exceeds one.

The model assumes conflict-free banking, ideal cache replacement, perfect load balance, nominal clocks, no instruction overhead, and no interference between kernels. Each assumption is the best case of the thing it abstracts. Real banking has conflicts; real replacement is LRU-ish and evicts things you wanted; real work distribution has tail effects; real clocks throttle. So the errors do not cancel — they compound multiplicatively in one direction, which is why the table above bottoms out at “modelled 80%, measured 40%”.

How to work with a systematically biased estimator, which is a more tractable situation than an unbiased noisy one:

• Use it for ranking, not for absolute numbers. If the bias is roughly common-mode across mappings, the model’s ordering survives even when its magnitudes do not — and ordering is what the search actually needs. This is the primary defence and it is why the approach works at all.
• Check that the bias is actually common-mode, because sometimes it is not. A mapping whose access pattern happens to be bank-conflict-free is penalised relative to one that is not, and the model cannot see the difference, so it can invert the ranking of two close candidates. The discipline is to take the top-$k$ from the model and measure those $k$, rather than trusting the argmax.
• Calibrate against whatever silicon you do have. Even for a new design, the previous generation exists. Fit the per-access energies and the derating factors against measured kernels on it, and carry the derating forward. This is standard practice in architecture teams and it is the difference between a model that is 30% optimistic and one that is 10%.
• Model the variance, not just the mean, where you can. Bank conflicts and load imbalance have known worst cases. A model that reports “1000 cycles nominal, 1400 worst case” supports a much better provisioning decision than one reporting 1000.
• Provision against the pessimistic end. Since the error is one-sided, sizing a memory system from the model’s optimistic traffic estimate produces a chip that is bandwidth-starved. Applying an explicit derating factor before committing capacities is not conservatism, it is bias correction.

The meta-point worth carrying: a biased model with a known sign is a usable instrument. The dangerous model is one whose bias varies with the thing being compared — which is exactly what happens when you evaluate a radically different design point (a wafer-scale part, a fully static machine) against a model calibrated on GPUs.

Because measurement is exact and expensive, and the expense is structural rather than incidental.

Autotuning a single kernel means compiling and timing thousands of configurations. Compilation is seconds; timing needs repeats to beat noise; and the space must be re-searched for every new shape, because a tile size tuned for $M=4096$ is wrong for $M=17$. In production that hits three hard walls:

• Shape explosion. Dynamic batch sizes and sequence lengths mean the shapes are not known ahead of time and there are far too many to tune each. This is the same problem the ML Software series hits with dynamic shapes, from the other side.
• Compile-time budgets. Nobody accepts an hour of autotuning on the first request. This is why torch.compile’s mode="max-autotune" is opt-in and why its cache is so important.
• Portability. Tuned results are per-device, per-driver, per-clock. A new SKU invalidates them.

So real systems are layered, and the layering is the actual answer:

1. Closed forms and heuristics for the common case — square tiles at $\sqrt{C/3}$, known-good shapes. Free, and usually within 10–20% of optimal.
2. A learned cost model trained on measurements, to rank candidates without running them. This is Ansor’s contribution: use measurement to train a proxy, then use the proxy to search broadly and measure only the top candidates. It is the hybrid, and it is where the field landed.
3. Measurement of the top-$k$ only, which recovers exactness where it matters while keeping the cost bounded.
4. Caching, aggressively, keyed on shape buckets rather than exact shapes.

The division of labour that emerges across the whole field is worth stating plainly, because it is not the one people assume: analytic models are for architects, hybrid learned models are for compilers, and pure measurement is for the final tuning of a handful of kernels that matter enough to justify it. Timeloop is not competing with Ansor — they run at different times, for different decisions, by different teams, and confusing their roles is how a hardware team ends up under-provisioning a chip because “the autotuner will figure it out”.

Into a stack of effects, each individually forgivable, that multiply. Attributing them in order is the standard post-silicon exercise and the numbers are depressingly consistent across projects.

Work down the levels:

• The model’s own optimism, ~1.3–1.6×. Bank conflicts, row locality, imperfect replacement, issue overhead, tail effects. Every item in the table above. This is the part a better-calibrated model would have caught, and it is typically the largest single contributor.
• Non-GEMM work, ~1.1–1.3×. The model priced the GEMMs. The workload also has norms, softmaxes, activations, residual adds, transposes and reshapes, which contribute few FLOPs and substantial memory traffic. Amdahl on the part nobody modelled.
• Communication not overlapped, ~1.1–1.4×. All-reduces, all-gathers and pipeline bubbles that the single-chip model did not represent at all. Module 11.
• Shape mismatch on real shapes, ~1.05–1.3×. The model evaluated aligned power-of-two shapes. The workload has vocabulary sizes of 50,257 and sequence lengths of 1,013.
• The compiler not finding the mapping, ~1.1–1.5×. The model assumed the optimal mapping. The compiler that ships is not the one in the study, and this gap is the largest one nobody puts in a slide. It is the subject of Module 14.

Multiply them and 80% becomes anywhere from about 44% at the optimistic end of every range down to 14% at the pessimistic end — the midpoints give 24%. Real large-scale training MFU lands in the 30–50% band, which says most deployments are doing better than the midpoints and nowhere near the best case.

Two conclusions worth taking seriously:

Model the whole workload, not the kernel. Almost every term above is an effect of composition — interference, non-GEMM remainder, communication, real shapes. A study that models GEMM in isolation is answering a question nobody asked. The architecture teams that get this right run end-to-end models with the layers, the collectives and the untuned remainder included, even though each component is modelled more crudely.

Budget for the compiler explicitly. If the study assumes optimal mappings and the compiler reaches 70% of them, the design is provisioned for a machine nobody will run. The honest move is to carry a compiler-efficiency factor as a named term in the model — and then to notice that improving it is often cheaper per unit of delivered performance than any hardware change under consideration. That observation is the reason this series exists, and it is where Module 14 ends up.