The expressivity–scorability ladder

What a submission’s generator may express, what each rung costs to score, and which rungs modern silicon actually uses — with the design decisions for the episodic MNIST task. Companion to Fixed or moving I/O order? and the scheduled-language RFC (#48). Continued in the Grid VM competition design. September 4, 2026.

1. The question

Submissions to the simplified Dally model are straight-line programs: no loops, no branches, no data-dependent addressing. That choice makes energy a syntactic property — the judge scores by reading the program, never by running it — and it is defended at length in the I/O-order note. But it has a hard consequence: program length is proportional to work. A 10¹²-operation computation is a 10¹²-line program; full-scale benchmarks are unwritable as traces (the “27 TB wall” that motivated RFC #48).

The obvious fix is to let submitters send the generator of the straight-line program rather than its expansion. The question is what the generator language may contain. Every construct added buys expressivity and costs scorability, and the costs arrive in a specific order. This note lays out that ladder, one rung at a time, and records which rungs this project’s tasks stand on and why.

2. Two tracks, one principle

A prior distinction dissolves half the problem. There are two different reasons to want loops, and they get different answers:

• Episodic-scale tasks (a few thousand stream bytes, programs under a few hundred thousand lines): the expansion fits in a file. Submitters may use any generator they like — Python, an LLM, anything Turing-complete — because the organizer never runs it. The submission is the expanded trace; the generator is the submitter’s private business. This is already how the sparse-parity leaderboard works in practice: entries are .ir files produced by generate_* functions that live outside the trust boundary.
• At-scale tasks (8192³ matmul, full-dataset training): the expansion cannot be materialized, so the schedule itself must be the submission — and now its language must be restricted. The restriction motive is scorability, not sandboxing: the judge must be able to compute the expansion’s exact energy without expanding it.

3. The ladder

The cliff is between (e) and (f), and it is a theorem, not a taste: once trip counts depend on data, boundedness — and with it cost — is undecidable (Buck). Rungs (a)–(d) preserve exact, closed-form, execution-free scoring; rung (e) preserves it in the worst-case reading; rung (f) does not preserve it in any reading.

4. Scoring technology, rung by rung

(b) Affine nests. Every operand read inside an affine nest has address b + s₁i₁ + … + s_di_d over a product of static ranges, so total read cost is a sum of ⌈√x⌉ over arithmetic progressions. That sum evaluates in O(1) per (loop, operand) pair via the closed-form antiderivative of ⌈√x⌉ — the mechanism of RFC #48, cross-validated bit-exact against the trace scorer on every expandable program. Judge time is microseconds at any scale.

(c) Static recursion. Cost obeys the recurrence the recursion defines: C(n) = a·C(n/b) + f(n) with a straight-line base case, unrolled numerically in O(log n) steps since depth is compile-time. Nothing is estimated; the recurrence is exact.

(d) Bijective maps. The observation that makes this rung free: if σ is a bijection on a static range, then Σ ⌈√σ(i)⌉ = Σ ⌈√i⌉ — permuting which iteration touches which address cannot change the multiset of addresses touched. Bit-reversal, stride permutation and XOR indexing therefore cost exactly what the identity map costs, and FFT and bitonic networks score as cheaply as dense loops. The verifier’s obligation is only to check bijectivity, which is why the maps come from a fixed library rather than as arbitrary expressions: for the library members bijectivity is a lemma, not an analysis.

(e) Modes. Score each of the k schedules statically. Charging the maximum keeps the score execution-free and gives hardware-honest semantics (provision for the worst path); charging the expectation requires measured selection frequencies from adjudication data and should be deferred until a task actually needs it. Reserving the syntax now costs one paragraph; retrofitting it later costs a redesign.

5. Is the restriction relevant to modern silicon?

Three observations say the static-bounds restriction is not a toy simplification but the constraint production ML compilers already live under:

• XLA lives on rung (b)–(c). TPU compilation requires static shapes and static trip counts; training steps compile to fixed-length loops; dynamic shapes are the documented exception, not the rule. CUDA Graphs likewise capture a fixed kernel DAG and replay it. The generator language proposed here imposes on submitters what these toolchains impose on themselves.
• The polyhedral school is rung (b) as a research field. Affine loop nests with static bounds are precisely the domain of polyhedral compilation (Pluto, MLIR’s affine dialect), of Halide’s algorithm/schedule split, and of Timeloop’s mapping spaces — the standard vocabulary for describing how accelerators walk loop nests. A schedule submission in this language is legible to anyone in that community on sight.
• Rung (c) is required for honesty about matmul. Affine nests alone cannot express Strassen — recursion with additions at each level is structurally outside a single nest — and an energy leaderboard for matrix multiplication that cannot express the sub-cubic algorithms would prejudge the very question it poses. Recursive tiling is also how RFC #48 maps schedules onto the physical hierarchy, so the construct pays twice.

What rungs (a)–(d) still cannot express is data-dependent work: unstructured sparsity harvesting, adaptive sampling, convergence tests. That exclusion is deliberate and priced (see the closed/open division argument in the I/O-order note); rung (e) is the reserved escape hatch for the commercially important middle case (MoE with a fixed capacity factor), and rung (f) belongs to an open division scored by simulation at small scale.

6. What generators buy beyond feasibility: parametric scoring

A trace has one size. A schedule with the problem size as a formal parameter has a cost formula: energy as a function of n, evaluated exactly at any size without re-scoring. Two consequences:

• Floors at every size. Known lower bounds (red–blue pebbling for dense linear algebra I/O; the Ω(n³/√M) family) are also formulas in n. A parametric submission can be reported as a ratio to the floor across the whole size range — “3.4× above the pebbling bound at every n” — which is a categorically stronger statement than a point comparison at one size.
• Asymptotic honesty. Whether a trick’s advantage grows, shrinks or vanishes with scale is visible in the formula. Trace leaderboards systematically overfit constants at the benchmarked size; parametric ones cannot hide the exponent.

7. The instruction-fetch fork

A separate design note’s red-team result forces one refinement. If program text is unpriced, the instruction stream is free ROM: a lookup table encoded as immediates costs Θ(K) tiny units instead of the Θ(K^3/2) that the same table pays in priced memory, so memorization is priced linearly rather than priced out. The fix is to charge instruction fetch. Precedent: the Hutter Prize has counted the decompressor’s size in the score for twenty years; and fetch/decode overhead dominating arithmetic is the canonical energy argument for specialization in the first place — a cost model with free fetch contradicts its own thesis.

But the ladder splits the right charge in two, and this is a genuine fork with physics on both sides:

Two constants, one per track, each stated with its physical reading. Leaving fetch unpriced is the one option the red-team result forecloses.

8. Where the episodic MNIST task stands on the ladder

The proposed MNIST task (in design; parameters from a separate empirical calibration) is deliberately a rung-(a) competition: 10-way 4-shot episodes at 8×8 grayscale arrive as a ~3,240-byte stream through the ports defined in the I/O-order note; a submission is an expanded trace of at most ~200,000 lines with per-executed-line fetch pricing; energy is a static property of the text. Consequences of that placement:

• No schedule language is needed at all. Submitters generate with whatever they like; the barrier to entry is a text file of thirteen opcodes plus recv/send. This serves the goal of a simple competition more than any language feature could.
• The interesting algorithms fit. An honest nearest-centroid or 1-NN episode program is ~10–30k lines — an order of magnitude under the cap — and the measured strategy spread (majority 10% → linear ~54% → centroid ~56% at 32 examples, against a ~93% resolution ceiling) leaves room for genuinely smarter circuits.
• Scale is someone else’s rung by design. Full-dataset MNIST training (~4.7×10⁷ input bytes) is exactly where the trace format dies and rungs (b)–(d) take over; that is the scheduled-language track of RFC #48, and the episodic task is its calibration corpus, not its competitor.

9. The decisions, with their pros and cons

Summarized in one sentence: the machine stays a circuit at every rung; loops, recursion and index maps are compression formats for circuits, admitted exactly as far as compression stays exactly scorable; and the one construct that would make cost depend on data is the one construct excluded from the closed division.

10. References

1. RFC #48, “The Scheduled Dally Language,” this repository — hierarchical affine schedules, recursive tiling, closed-form read-cost summation.
2. “Fixed or moving I/O order?” — companion note: stream ports, determinacy, the closed/open division split.
3. J. T. Buck, “Scheduling dynamic dataflow graphs with bounded memory using the token flow model,” PhD thesis, UC Berkeley, 1993 — undecidability past static rates.
4. U. Bondhugula et al., “A practical automatic polyhedral parallelizer and locality optimizer” (Pluto), PLDI 2008.
5. C. Lattner et al., “MLIR: Scaling compiler infrastructure for domain specific computation,” CGO 2021 — the affine dialect.
6. J. Ragan-Kelley et al., “Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines,” PLDI 2013 — the algorithm/schedule split.
7. A. Parashar et al., “Timeloop: A systematic approach to DNN accelerator evaluation,” ISPASS 2019 — mappings as first-class scored artifacts.
8. V. Strassen, “Gaussian elimination is not optimal,” Numerische Mathematik 13, 1969.
9. J. Cooley and J. Tukey, “An algorithm for the machine calculation of complex Fourier series,” Math. Comp. 19, 1965.
10. K. Batcher, “Sorting networks and their applications,” AFIPS 1968.
11. M. Frigo, C. Leiserson, H. Prokop, S. Ramachandran, “Cache-oblivious algorithms,” FOCS 1999 — static divide-and-conquer as the hierarchy-friendly discipline.
12. J.-W. Hong and H. T. Kung, “I/O complexity: the red-blue pebble game,” STOC 1981.
13. A. Aggarwal, B. Alpern, A. Chandra, M. Snir, “A model for hierarchical memory,” STOC 1987 — the distance-priced RAM (HMM) this cost model instantiates with f(a) = ⌈√a⌉.
14. W. J. Dally, “On the model of computation: point,” CACM 65(9), 2022 — fetch/decode overhead as the energy argument for specialization.
15. M. Hutter, the Hutter Prize (prize.hutter1.net) — program size counted in the score.
16. OpenXLA / TensorFlow XLA documentation — static shapes and trip counts as compilation requirements; NVIDIA CUDA Graphs — captured static kernel DAGs.
17. N. Shazeer et al., “Outrageously large neural networks: the sparsely-gated mixture-of-experts layer,” ICLR 2017; W. Fedus et al., “Switch Transformers,” JMLR 2022 — capacity-factor routing, the rung-(e) target.
18. C. Yadav and L. Bottou, “Cold case: the lost MNIST digits” (QMNIST), NeurIPS 2019 — the held-out adjudication pool for the episodic task.
19. S. Greydanus and D. Kobak, “Scaling down deep learning with MNIST-1D,” ICML 2024 — procedural generation as a memorization defense.