The Grid VM: competition design and feasibility

A concrete design for the rung-(a)–(e) machine — language, scoring function, adjudication protocol — and what it costs to judge episodic MNIST at three tiers on a laptop. Companion to the expressivity–scorability ladder and Fixed or moving I/O order? September 4, 2026.

1. The brief, and how this note was produced

The ladder note ends with a decision: take the generator language all the way down to rung (e) — straight-line code, affine loop nests, static recursion, a bijective index-map library, and data-dependent modes — on a von Neumann machine: one sequential control unit at the origin of a 2-D grid of byte cells (1 µm pitch, 1 fJ per byte-micron moved, c/160 propagation), one serial input port, one serial output port. The task is episodic MNIST at three tiers — 3×3 images with 600 train / 600 test, 9×9 with 6,000/6,000, 28×28 with 60,000/60,000 (QMNIST supplying the extras) — resampled from the pooled corpus at every evaluation. The harness streams the training set (images and labels — whether blocked or interleaved per example is itself a scoring lever, decision D6 of §11), then the test images; the program must emit test-label predictions through the output port; a fixed accuracy target gates entry, and separate leaderboards rank energy, time, and area.

2. Three implementation routes

Route A — assembly level (“GridASM”). Flat opcode text, a strict superset of today’s trace IR, plus structured repeat/proc/mode blocks. The address is the cost: every line’s price is visible to the writing LLM and the reviewing human, and no compiler sits inside the trust boundary. Its review found the continuity claim overstated — once ports are priced, legacy free-input records are not score-comparable anyway — and tier-3 networks in hand-placed assembly are laborious.

Route B — structured DSL. Placed arrays (place W : i8[10][9] at (4,0)), affine for, recursive defs with compile-time size parameters (compile-time-ness enforced by a kind system, not analysis — if may only test size expressions, so it is specialization, not branching), mode blocks, recv()/send. The DSL lowers to a one-page Schedule IR; the lowering is untrusted, and the SIR is the scored artifact, differentially tested by expanding to traces at tiny sizes — the RFC #48 methodology.

Route C — reuse survey. The decisive negative result: no existing system computes this scoring function, so reuse only ever buys the front end. MLIR’s affine dialect is the right vocabulary but an unacceptable dependency (a multi-GB LLVM build to parse 40-line files); Halide and TVM cannot express static recursion, and a matmul leaderboard that cannot express Strassen prejudges its own question; WebAssembly and RISC-V solve a sandboxing problem this design does not have (the only native code that ever runs is emitted by the judge itself from the validated schedule, so Wasm’s sandbox buys nothing) while creating a polyhedral-raising problem it cannot afford. The winner inside route C: an embedded Python builder library emitting canonical schedule text. Agents author in Python with eager validation — a non-affine index is a TypeError on the submitter’s machine — and the judge parses only the text. This formalizes what the repo already does with generate_*() functions.

3. The recommended stack

Converge B and C: a Python builder (authoring layer, outside the trust boundary) emits a canonical schedule text styled after MLIR-affine notation (the reviewed and scored artifact), consumed by a Rust judge of roughly 2–3k new lines atop dally-eval. In every route surveyed, the grammar itself is the rung enforcement: while is unrepresentable — verification by absence, the cheapest verifier there is. Hand-written schedule text remains a legal submission, so the trace-tuning culture is not orphaned. Tier-1 flavor of the scored text:

schedule tier1_centroid          # episodic MNIST tier 1 (3x3, 600/600)
                                 # assumes per-example interleaved train records (D6);
                                 # blocked framing instead forces retaining all 5.4 kB
                                 # of train images until the labels arrive
param NTRAIN=600, NTEST=600, P=9, K=10
alloc img : u8[P]      @ 2       # current example, hottest cells
alloc cnt : u16[K]     @ 16
alloc sum : u16[K,P]   @ 40

for t in 0..NTRAIN:
  for p in 0..P: recv img[p]
  recv lbl
  mode lbl -> c in 0..K:         # rung (e): the label routes the update
    add  cnt[c], cnt[c], 1
    for p in 0..P: add sum[c,p], sum[c,p], img[p]

# ... centroids, then classify the test stream, send NTEST predictions

The mode here is load-bearing, not decorative: labels index accumulators, which pure rung (b) can only emulate by touching all K classes with indicator multiplies — several times the energy of one dispatched arm.

4. The language: constructs and the four load-bearing constraints

Adversarial review produced four constraints that must be in the v1 grammar — each has a concrete exploit or a scoring breakdown without it:

1. Port balance. Every arm of every mode must have identical (recv, send) counts. Necessity: one unbalanced selector makes the number of consumed stream bytes data-dependent, and every later recv then reads a data-dependent tape position — Boolean-dataflow territory, the undecidable side of the I/O-order note’s cliff. Sufficiency: by induction on block structure, balanced modes keep whole-program (recv, send) counts static, so every recv’s tape index is fixed and all scoring stays execution-free.
2. Mode dispatch must be priced — as a read at distance ⌈√(total static bytes of all arms)⌉. Unpriced, a nested 512-leaf mode is a free associative memory: a hardcoded pattern→label table wins the tier-1 energy board 50–100× over honest centroid. This is the ladder’s §7 ROM attack tunneling through control flow; the price restores the √K-per-access discipline of priced memory. Cap total arms (~64) and nesting (≤3).
3. Index maps are banned inside mode arms. Max-over-arms does not commute with the permutation-invariance rewrite; a four-iteration counterexample undercharges 8 → 5. (Outside arms the invariance is exact and maps stay free.)
4. Recursion must be offset-affine. Per-instance cost must be affine in the view base offset, propagated as (a, b) coefficient vectors through the instance DAG. Naïve “memoize on the size tuple” is wrong: Strassen at 8192 has ~14 memo nodes but 7¹³ ≈ 10¹¹ call sites at distinct offsets.

Semantics that must be pinned before anyone writes a program (every worked example produced during the design run had at least one overflow bug until these were fixed): u8/i16/i32 widths as adjacent cells, little-endian; wrap mod 256 (two’s complement); widen-before-op; x/0 = 0; all cells zero at program start; one fresh run per episode (no cross-episode state); out-of-range mode selector traps and the episode scores zero; blocking recv only — no emptiness test, no clock.

5. The scoring function

Distance metric. Cells are 2-D; distance is Chebyshev, d(x,y) = max(x,y). Roughly c² cells lie within cost c, reproducing the 1-D model’s ⌈√a⌉ shells — roughly, because the boundary counts differ (the quadrant shell holds 2c+1 cells against the 1-D shell’s 2c−1), which is why a canonical lin(a) embedding published with the spec, not a slogan, is normative for legacy-compatible 1-D addressing. The payoff: max of affine coordinates is piecewise-affine, so rung-(b) sums become lattice sums of affine forms rather than √-staircases.

Energy. E = Σ_reads d(p)  +  4 fJ · static lines  +  0.1–1 fJ · issued instructions  +  n_recv·E_in  +  Σ_sends (d(s) + E_out). Writes are free in v1 (the write of op k is typically the read of op k′; the calibration constant absorbs the round trip) — owner decision D2. The per-issued-instruction fetch floor is load-bearing: with a per-iteration-only charge, compute parked at the origin becomes essentially free and the episodic track’s executed-line floor vanishes. E_in matters enormously and 1,000 fJ is wrong: the I/O-order note’s own resident-vs-restream break-even sits at ≈4.6×10³ fJ/byte, and DRAM-interface figures run higher still. Recommendation: E_in = E_out ≈ 5,000 fJ, fixed and published before launch — it sets the economics of every attack in §7.

Closed forms, honestly stated. Single-variable progressions use the ⌈√⌉ antiderivative of RFC #48. Multi-coefficient affine addresses give quasi-polynomials with floor-sum corrections (Ehrhart of rational polytopes), not pure polynomials — still exact and fast via banded lattice counting, O(√A_max) bands ≈ 10⁴ integer evaluations at A_max = 10⁸ — but the spec must name the floor-sum evaluator as normative rather than claim “O(1) polynomial.” Recursion scores by the memoized recurrence over offset-affine instances (§4.4). Modes score Σ_encounters max_arm, composed inside-out through loops; where arm cost depends on enclosing indices, the judge enumerates encounters up to 10⁶, beyond which arms must be cost-balanced — a declared v1 restriction, not a silent one.

Time (v1): sequential issue. T = N_issued · 1 ns + Σ d(p)/1.875 µm·ns⁻¹ + port terms. Same summation engine as energy, closed-form at every rung, bijection-invariant. The honest consequence: TIME correlates with ENERGY and tier-3 sequential time is measured in days (§9) — the leaderboards diverge only through the port and fetch weightings, and the issue/flight-overlap rule must be stated explicitly. Time (v2): dataflow critical path — affine schedules via Karp–Miller–Winograd, a small LP per nest, max-plus recurrences for recursion — is well-posed and closed-form, but bijection invariance fails there (a bit-reversal stretches wires; physically real), so library maps would need per-map dilation lemmas. Run v2 as a separately-scored spatial division; do not blend it into v1.

Area. Origin-anchored bounding square of touched cells, in µm² (touched-cell count is gameable by scatter). Union over mode arms — hardware provisions every arm. Max of an affine form over a box sits at a corner: O(2^d) evaluations per operand.

6. Adjudication: running the program for accuracy

Cost scoring never executes anything; accuracy requires actually running the program on resampled episodes. The executor is an embedded Cranelift JIT in a prebuilt universal judge binary (no toolchain needed on the judge laptop; the switch-dispatch interpreter is retained as a differential-testing oracle, and transpile-to-C via the macOS CLT clang is the fallback). Loops, recursion and modes emit as native loops, functions and bounds-checked switches; the grid is a lazily-zeroed mmap sized by the area bound.

Fuel is free. For rungs (a)–(e) the executed-op count is itself closed-form (static trip counts; worst arm for modes), so over-budget submissions are rejected without being run — evaluation denial-of-service is structurally impossible. A per-block runtime fuel counter (<1% overhead) remains as defense-in-depth against judge bugs.

Episode protocol. Seeds are derived, not drawn — but keyed: seed_j = SHA-256(server secret ‖ submission bytes ‖ tier ‖ j). Without the secret term a submitter simulates all episodes offline and ships the answer sequence as immediates — 100% accuracy at near-zero energy; this was found as a fatal hole in the first draft of the spec. Pooled accuracy over K episodes against the target, with train/test disjoint within each episode and exactly n_test sends required. Per-episode binomial noise is ±2.0 / ±0.5 / ±0.09 percentage points at the three tiers, and one dead set line yields 256 minable seeds worth +5.5 pp at K=1 on tier 1 — so K = 50 / 10 / 3 per tier, which shrinks the mined maximum to about +0.8 pp at tier 1 while costing the judge nothing material (§8).

7. The embedded-weights decision

The red team’s central finding: the attack that defines this competition is not a scoring exploit but a training-data exploit. The pool is public; a submitter pretrains offline and ships int8 weights as immediates — 100 B for a tier-1 linear head, ~80 KB for a tier-3 MLP at ~98%. Embedding cost is a ~10⁻⁵ tax; what it skips is in-episode training, roughly 15/16 of tier-3 energy. Unmitigated, the “learning” axis is dead code and the benchmark measures inference circuits. Mitigation triage, with review-corrected taxes:

The three options that actually work, to be chosen explicitly: (a) accept it — rename the closed division episodic inference energy and run in-episode learning as a separate division; (b) procedural episode generation (MNIST-1D-style generative parameters redrawn per episode, so no finite pool exists to pretrain on); (c) per-episode invertible mixing (GF(2)-affine on pixel bytes), which makes recovering the transform equivalent to learning but destroys spatial priors and every calibration number. Recommendation: (b) for tiers 1–2, decide tier 3 after deciding whether convolutional architectures are a protected species. Label permutation is layered under all of them.

Two attacks recorded as dead: the tier-1 “Bayes table” (measured: 59,725 of 60,000 3×3 images are distinct at 8-bit depth, so a top-1000-pattern table scores ~12%), and pool-lookup by linear scan (arithmetic: ~6×10¹² trace lines at tier 3, fetch-priced into oblivion).

8. Judge cost per tier

Cost scoring is 0.1–4 ms per submission at every tier (parse + corner checks + ≤~36,000 closed-form evaluations at 50–200 ns each), anchored by the measured scoring-at-scale result: 0.3–3 ms to score a 1.1×10¹²-instruction schedule. Even a pure-Python fallback judge scores in 5–100 ms. Tier changes the integers, not the cost. Adjudication is the only real expense (Intel MBP ≈ 3×10⁸ op/s interpreted, ≈1.2×10⁹ JIT single-stream, derived from the dally-eval anchor of ~1.55×10¹⁰ op/s aggregate under multi-instance batching — batching that is unavailable here because one training run is a sequential dependence chain):

Memory stays under ~1.5 GB worst case (lazily-zeroed grid caps of 1 MB / 16 MB / 256 MB per tier plus one shared ~110 MB corpus). A 20-finalist tier-3 leaderboard re-score is a ~3 h overnight job on any 8-core machine; a cluster is never needed. One flag to set consciously: the tier-3 laptop cap has ~3× headroom over the plain-MLP upper bound, ~1.5× over LeNet-scale at 3 byte-ops/MAC, and below 1× at a realistic 4–6 byte-ops/MAC — as drafted it can exclude honest LeNet training, unlike the 10× margins of the other tiers.

9. What winning programs look like

Working-set model: average operand distance ~√W for the live hot working set W; each MAC ≈ 2 reads + fetch. Energies are compute-only; the port floors below are additive (dominant at tier 1: the 57 nJ in-stream floor is ~11× centroid compute). Areas assume the train section is either consumed in one pass or replayed by the harness on static request (decision D6); if instead the stream arrives exactly once, multi-epoch training must buffer the train set on-grid, and the tier-3 area floor becomes ~4.7×10⁷ cells (the 1-NN row’s figure) with a ~1% energy surcharge per resident sweep. At E_in = 5,000 fJ the two régimes are within ~10% in energy at tier 3 (2.2×10¹¹ fJ per resident sweep vs 2.35×10¹¹ fJ per re-streamed epoch) — the resident-vs-restream lever of the I/O-order note, genuinely contested. All rows re-derived by an independent reviewer.

Anchors. The measured A100 point (this repo, matmul/a100_8192_dtype_energy_results.json): 8192³ int8 GEMM = 0.904 J board energy above idle = 1.64 pJ/MAC at 5.5×10¹¹ MACs — note the factor-of-exactly-2 convention hazard against the 1.1×10¹² multiply-plus-add count; pin one convention in the rules. Tier-3 MLP training (5.2×10¹¹ MACs) scores 0.38 J in the grid model against 0.86 J of A100 int8 arithmetic for the same MAC count — agreement within 2.3× — and the judge-scored blocked 8192³ schedule lands at 0.119 J (216 fJ/MAC), 7.6× below the A100. The femtojoule story holds. The hazard: applying the √W rule unblocked to the A100’s 384 MiB resident set predicts ~22 J, 24× over measurement — publish the working-set convention with the task, or self-estimates and official scores will disagree by an order of magnitude at tier 3.

Stream floors never decide a ranking: 11.4 kB / 0.98 MB / 94 MB in-streams cost 5.7×10⁷ / 4.9×10⁹ / 4.7×10¹¹ fJ at E_in = 5,000 — at tier 3 that is ~10⁻³ of MLP training energy. The floor makes “read everything at least once” well-defined and prices ingest, no more: as the red team notes, a recv into a dead cell launders nothing, so what actually polices the embedded-weights attack is the §7 protocol, not E_in.

10. Accuracy targets: what measurement corrected

An adversarial reviewer ran real 600/600 MNIST episodes (20 draws, block-mean downsampling) rather than trusting literature extrapolations. Two draft recommendations flipped outright, and a third was conditioned by an analytic re-derivation:

1. Tier-1 centroid is 48.2 ± 2.1%, not ~56%; linear@600 is 50.5%; 1-NN@600 is 54.0%. A 50% target would kill centroid; set tier 1 at ~45% so at least three cheap families clear it.
2. 9×9 linear measures 84.8% (full data), so the drafted 88% tier-2 target would exclude linear entirely; set tier 2 at ~80–82% if the cheapest learner should stay in play.
3. Tier 3 at 97.3% works only because the task pins a 60k test set (σ = 0.07 pp); at MNIST’s usual 10k test set 1-NN (96.9%) sits 2.4σ from threshold and passes ~1% of draws. Never place a target at 97.0.

One structural consequence falls out of the trace arithmetic: tier 2 is ~1.2×10⁷ trace lines and tier 3 is ~10⁹ lines (a 10–19 GB file) — tiers 2 and 3 are schedule-track only, declared in the rules from day one; tier 1 runs dual-track and serves as the trace-vs-schedule cross-validation corpus, per RFC #48’s discipline.

11. Open decisions

Summarized in one sentence: the machine can go to rung (e) without giving up execution-free scoring — milliseconds to score, minutes to adjudicate, laptop throughout — and the one decision that actually shapes the competition is not in the language at all, but in where the episodes come from.

12. References

1. “The expressivity–scorability ladder,” this repository — rungs (a)–(f), the fetch fork, the episodic MNIST placement.
2. “Fixed or moving I/O order?” — ports, determinacy, the resident-vs-restream break-even, the closed/open division split.
3. RFC #48, “The Scheduled Dally Language” — closed-form read-cost summation, trace cross-validation methodology.
4. J. T. Buck, “Scheduling dynamic dataflow graphs with bounded memory using the token flow model,” PhD thesis, UC Berkeley, 1993 — undecidability past static rates; the port-balance rule’s justification.
5. R. M. Karp, R. E. Miller, S. Winograd, “The organization of computations for uniform recurrence equations,” JACM 14(3), 1967 — affine schedules for the v2 time division.
6. V. Strassen, “Gaussian elimination is not optimal,” Numerische Mathematik 13, 1969 — the rung-(c) flagship and the offset-affine recursion requirement.
7. M. Hutter, the Hutter Prize — program size in the score; precedent for priced fetch.
8. S. Greydanus and D. Kobak, “Scaling down deep learning with MNIST-1D,” ICML 2024 — procedural generation as the memorization defense (option b of §7).
9. C. Yadav and L. Bottou, “Cold case: the lost MNIST digits” (QMNIST), NeurIPS 2019 — the extra examples; also why a “held-out” pool is public.
10. M. Horowitz, “Computing’s energy problem (and what we can do about it),” ISSCC 2014 — off-chip access energy grounding E_in.
11. W. J. Dally, “On the model of computation: point,” CACM 65(9), 2022 — the physical calibration’s source model.
12. This repository: matmul/a100_8192_dtype_energy_results.json (measured A100 anchor), scoring-at-scale/ (measured 0.3–3 ms closed-form scorer; blocked-GEMM judge score), sparse-parity/README.md (dally-eval throughput anchor).