Research results · autonomous run · two phases · 8 August 2026
A function’s complexity as its distance from a constant.
Not a program that computes f(x). A sequence of overwrites, each one naming a subset of the
input domain using structure the type already provides, and repainting the function’s value there.
Complexity is the cheapest such sequence, in bits. Learning is picking the cheapest one consistent with the data.
The second phase asked what that buys you. Answer: sample efficiency is governed by the target’s description length in the available structure, and nothing else the experiments could resolve. On a domain where the truth is exactly expressible, that is worth three orders of magnitude against a neural network.
The whole domain, repainted rule by rule
19 683 fields — one pixel each. Hover to inspect. Recomputed live.
Layout is the field index in base 3: horizontal position encodes cells 1–5, vertical position cells 6–9.
The self-similar texture is the type Field = Coor² → Cell.
The brief
A deliberately non-standard notion of complexity
The task set one hard constraint: do not turn this into program synthesis. The object whose complexity matters is the extensional function itself, the value table, and a description is a sequence of structurally defined transformations that turns a constant function into that table.
The second constraint was methodological: find the smallest set of mechanisms. If the formalism starts accumulating auxiliary states, special cases and bookkeeping, that is evidence the abstraction has not been found yet. Singletons, orbits, multiplicity classes and threshold regions must not be four primitives; they must be four faces of one.
What came back
- Three primitives: a structured domain, a priced subset description, one overwrite. Everything else is derived.
- A reduction that turns minimising a certificate into a shortest path in a small lattice, and never touches the 4^19683-vertex function graph. Verified against brute force.
- Exact optima for all 256 functions on two 8-point domains, so heuristics can be scored against truth, not against each other.
- An incremental learner that reaches the true optimum on 96% of them, and recovers tic-tac-toe from a quarter of its table.
- Two honest failures, reported below rather than buried: a rare-class accident, and a cost model that is only an upper bound on the intended one.
And what the second phase added
- A quantitative law: ablate the type’s structure and the whole learning curve shifts by about what the target’s description gains in bits. Efficiency law.
- Order invariance — the learner is now a deterministic function of the observation set, with contradiction as an absorbing state.
- A harder domain: 2 598 960 poker hands, ten classes, the rarest with four members. Poker.
- A direct comparison with a neural network, including where this method should be expected to lose. vs a neural net.
Deliverable A
Three primitives
Everything in the project is one of these, or is derived from them.
P1
Structured domain
A finite set presented by a type expression over bare sets with +, ×,
→. The expression induces an automorphism group and a family of derived maps
q : X → V into structured value spaces.
P2
Priced subset description
A walk through a prefix-free choice tree; each node charges log₂(#options). The subset is a fiber of a tupled derived map. Descriptions are syntax; subsets are semantics; equal extensions collapse to the cheapest description.
P3
Overwrite
The single transformation.
TS,y(g)(x) = y if x ∈ S
= g(x) otherwise
Structure generating structure
The interesting question was never “what is a subset” but “what makes a subset cheap”. Four canonical operations generate the whole map family, and the fourth is just “do it again to what you got” — which is where the higher-order structure the brief was hunting for actually comes from.
The cost model
Every atom is priced by the choices its derivation makes. Nothing else is charged.
With |Y| = 4 the constant start costs 3 bits and every rule pays 3 bits of overhead. Everything above that is structure you had to name.
Where the bits go
pick an atom familyFact 1 — the singleton is not an exception
A single point is the fiber of the tupled evaluation map over all nine of its cell values: nine choices, full price. There is no “change one point” primitive; there is only structural specification, continued until nothing is left to share. Universality follows for free, and complexity degrades smoothly to the cost of writing the table out, which is exactly what the tiny-domain experiments measure.
Fact 2 — the settled-set reduction
Later overwrites win, so only the last write at each point matters. Read a certificate backwards: rule i settles the points of Sᵢ that no later rule touches, and f must equal yᵢ there. So:
This is the discrete geometry the brief was reaching for. The naive picture (functions as vertices, overwrites as weighted edges) is correct; the test suite confirms it by brute force on a micro-domain. It is just useless directly. The reduction replaces it with a graph that never mentions intermediate extensions at all.
Instrument
Take a field apart
Click cells to cycle empty → X → O. Everything on the right is derived from the type, then fed to the learned certificate, by the same code path the experiment used, re-implemented here and checked against it.
- field index
- 0
- counts (X,O,·)
- 0, 0, 9
- #X − #O
- 0
- N₍₃,₀,₀₎ · N₍₀,₃,₀₎
- 0 · 0
- line profiles
Rules apply top to bottom and the last match wins. That is the whole semantics. It is also why the learned simple certificate is cheaper than the hand-written one in the brief: Draw needs no “and no winning line” clause, because the two win-rules overwrite it afterwards.
Deliverable E
What was learned, and what it cost
Two targets. simple is the extension of the hand-written certificate in the brief. legal is the stricter reachable-terminal classification; its class sizes reproduce the known 626 / 316 / 16 counts exactly, which is a real check on the implementation, not a formatting choice.
START: everything → Illegal [ 3.00 bits] OVERWRITE #Empty=0 → Draw [ 12.81 bits, |S|=512] OVERWRITE N(0,3,0)≥1 → OWon [ 14.40 bits, |S|=4435] OVERWRITE N(3,0,0)≥1 → XWon [ 14.40 bits, |S|=4435] ────────────────────────────────────────────── TOTAL 44.61 bits, 3 rules · 100.00% on 14 809 unseen
START: everything → Illegal [ 3.00 bits] OVERWRITE #X−#O=1 & N(0,3,0)=0 & N(3,0,0)≥1 → XWon [ 36.95 bits, |S|=626] OVERWRITE #X−#O=0 & N(3,0,0)=0 & N(0,3,0)=1 → OWon [ 36.95 bits, |S|=316] OVERWRITE N(1,2,0)≥4 & N(2,1,0)≥3 → Draw [ 25.80 bits, |S|=44] ────────────────────────────────────────────── TOTAL 102.70 bits, 3 rules · 99.65% on 14 729 unseen
Verified here, in your browser
The table is not copied from the run log. This page enumerates all 19 683 fields, recomputes both targets and both certificates from the definitions, and fills the numbers in. If the reimplementation disagreed with the reported run, you would see it.
| Rule | Bits | |S| computed | |S| reported | Points it settles | Semantically exact? |
|---|
Prediction quality against the alternatives
| Method | Model bits | Test accuracy | Notes |
|---|---|---|---|
| Learned certificate (legal) | 102.7 | 99.65% | 3 rules; X and O rules exact |
| Learned certificate (simple) | 44.6 | 100.00% | 0 errors of 14 809 |
| Memorise the training labels | 9 908 | — | predicts nothing off-sample |
| Majority class | ~2 | 95.12% | the bar a rare-class problem sets |
| 1-nearest neighbour, Hamming on cells | 5 000 rows | 94.30% | below majority; metric locality is the wrong bias here |
| Random labels, n=1 000 | 938 | 86.00% | below majority; every accidental rule that fires off-sample is wrong |
1-NN losing to the majority class is worth a second look: it is not a broken baseline, it is the point. Two fields one cell apart routinely have different labels, so distance in cell-space carries almost no signal. The structural language is not competing on data efficiency. It is competing on having the right notion of nearby.
The core claim
Natural functions get short certificates. Random ones do not.
The brief was explicit that high accuracy is not the interesting outcome. The interesting outcome is an asymmetry: the intended function compresses dramatically, and a random labelling of the same domain, through the same language and the same learner, does not. If random labels got short certificates, the coding scheme would be leaking information.
| Run | n | Raw repairs | Raw bits | Recompressed | Rules | Bits / example | Test acc. |
|---|
The raw column is the certificate before recompression: one rule per repair, hundreds of bits. Almost all of the compression is done by the local moves, not by the incremental pass, which is the argument for keeping both.
Deliverable C
Ground truth on domains small enough to solve
Before tic-tac-toe: two 8-point domains where the true minimum certificate can be computed for every one of the 256 boolean functions by exhaustive Dijkstra over settled sets. This is what makes the rest of the project falsifiable: the incremental learner is scored against optimality, not against another heuristic.
Selected function
Its provably optimal certificate on T1
Cost
Three sanity results that had to hold
- Reduction is exact. On a micro-domain the settled-set optimum equals brute-force Dijkstra over all |Y|^|X| functions, for every target. The compression of the geometry loses nothing.
- No leakage. Random functions land near the median and the worst function sits at extensional cost. A prefix-free code cannot compress noise, and empirically it does not.
- Planted certificates. For 200 random 2-rule certificates the exact optimum is ≤ the planted cost in 100% of cases.
The named cases
| Function | T1 | T1′ | Optimal description |
|---|---|---|---|
| constant | 2.00 | 2.00 | no rules |
| dictator x[0] | 8.58 | 8.58 | one evaluation fiber |
| majority | 10.58 | 24.92 | a threshold on a count |
| singleton {aaa} | 10.58 | 15.75 | it is the count-fiber #a=3 |
| singleton {aab} | 15.17 | 15.75 | x[2]=b & #a=2 — successive refinement |
| parity | 19.17 | 31.51 | two count fibers |
| worst case | 28.34 | 29.51 | ≈ writing the table out |
The two singletons are the argument in miniature. {aaa} is symmetric, so it is already a count fiber and costs the same as majority. {aab} is not, and has to be refined into place at full price. Same mechanism, different residual symmetry.
Deliverable D
Repair is the right shape. It is not sufficient alone.
The brief’s main algorithmic hypothesis was that a wrong prediction should trigger a small local search: the cheapest describable subset containing the offending point that contradicts nothing already seen, rather than resynthesis. That held. What it needed on top was a set of moves that undo choices.
The finding that mattered
The moves that repair a certificate are edits of the choice tree that prices it. Adding an atom is making one more choice; removing one, or replacing it with something broader, is undoing a choice. Lifting prof[row1]=(3,0,0) to N₍₃,₀,₀₎ ≥ 1 literally forgets which line. That is what generalisation is here. The search never manipulates syntax trees; it walks the cost structure itself, and semantically equal descriptions collapse because everything is memoised by extension.
And the global greedy baseline (cost-effectiveness covering, the textbook move) is worse than incremental repair (9% optimal vs 43%). It commits early to large rules that force expensive later patches. That is direct evidence for the brief’s hypothesis about the shape of the search.
The four local moves
- prune — drop a rule whose removal keeps the certificate consistent. Principled.
- broaden — delete a choice point from a description, then re-specialise minimally if the broader rule now claims points of another class. Principled: it is the ∃-lift along a structural family.
- merge — replace several same-output rules by one, found by the same search with “must contain a point” generalised to “must contain a set”. Added during the project, in response to a failure; improved every configuration.
- replay — re-run on a reordered stream. Honestly labelled as engineering, not theory. That it still contributes means the local move set is incomplete.
When greedy repair fails
Two characteristic failures, both named and measured:
- Tiling — a run of individually-cheapest medium subsets where one general rule plus exceptions was cheaper.
- Order traps — an early cheap rule that forces expensive later patches.
Roughly 40% of tiny functions need some recompression; about 4% are still not optimal even with the best of ten presentation orders. Order dependence is the residual, and it is reported rather than averaged away.
Then the order dependence was removed
A learner whose answer depends on the sequence its examples arrive in is reporting something about the sequence, not about the function. Phase II makes the certificate a deterministic function of the observation set: the observations form a join-semilattice of partial functions ordered by extension, observe(x,y) is a join, and the batch learner sorts that set into a canonical order (largest class first, then class index, then point index) before running the same incremental machine with deterministic recompression. Any permutation of the input now yields a byte-identical certificate.
The lattice is completed with a top element ⊥. Joining a point that contradicts one already observed yields ⊥, which is absorbing: no certificate is admissible for it, so the learner reports a contradiction instead of quietly arbitrating between two labels for the same input. Both properties are tests, not prose.
Determinism was not paid for
The canonical order is a good order, not merely a fixed one. Against the 256 exactly-solved functions it beats the average random presentation:
| Learner | Optimal | Mean | Worst |
|---|---|---|---|
| single random order | 72.7% | 1.040× | 1.38× |
| canonical batch (deterministic) | 75.8% | 1.041× | 1.38× |
| best of 10 random orders | 95.7% | 1.004× | 1.13× |
The gap to best-of-ten is the honest price of determinism. Closing it does not require giving up order invariance — a canonicalisation that deterministically tried a few structurally distinct orders (rarest class first as well as largest) would recover part of it. That is item 5 in what to do next.
Phase II · the law
Efficiency is not a property of the algorithm. It is a property of the type.
Fix the target — tic-tac-toe legal. Fix the learner. Take away structure the type induces, one family at a time, and measure. Every curve below is the same algorithm learning the same function; the only thing that changes is which derived maps it is allowed to name subsets with.
Learning curves under structure ablation
IID samples · deterministic batch learner · mean over 3 seedsCurves order themselves by description length
The certificate size each library converges to — about 115 bits with everything, ~300 without count comparisons, thousands without the line family — is the same ordering as the accuracy at every sample size. Full structure reaches 95% from 125 examples; without the line family it needs more than 4 000 and never gets there. That is a 30–60× difference in data, from a change to the type, not the algorithm.
A wrong language is worse than none
Cells-only plateaus at 88.4% — below the 95.1% you get by answering “Illegal” to everything — with a certificate that grows linearly in the sample. It is memorising patterns, and every memorised pattern-rule overclaims off-sample. Guessing the majority class would be better.
With poor structure, more data can hurt
Switch to bits and follow no-lines: at n=2 000 it is 93.1% and 2 001 bits; at n=4 000 it has dropped to 90.8% and quadrupled to 6 020 bits. Each new exception slice is another accidental predicate. The bloat is the diagnosis — the learner is reporting, in bits, that it has the wrong type.
The same law against target complexity
Hold the structure fixed and vary the target instead: plant random certificates of 1, 2, 4, 8 and 16 rules and learn them back. The x-axis below is not the planted size but the size the learner recovers at n=4 000 — because the planted cost is only an upper bound, and the learner routinely beats it. One 8-rule, 145.6-bit plant came back at 16 bits: its later rules had overwritten most of its earlier ones, and the short description of the resulting extension is what complexity actually means here.
| Rules | Planted | Recovered | n=250 | n=1 000 | n=4 000 |
|---|
Bits are the certificate at n=4 000; percentages are held-out accuracy. The last row is a genuinely hard extension: its size was still growing at n=4 000, and its learning curve is correspondingly the slowest of the grid — exactly the coupling the formalism predicts.
What the two halves add up to
Error at fixed n rises monotonically with κ — 17 bits gives 0%, ~60 gives 0.3%, ~90 gives 0.7%, ~130 gives 1.9%, ~2 000 gives 9.6% — consistent with err(n) ≈ c·κ/n, and every run sits far inside the Occam bound (κ·ln2)/n. Combined with the ablation: as far as these experiments can resolve, the only property of a target that governs how much data it takes is its description length in the structure available. That is one number, and the formalism computes it.
Phase II · asking better questions
The “why not 100%?” was three different questions
The residual errors of phase I looked like one failure mode. They are three, they have different causes, and only one of them is fixed by more data.
Precision — accidents
A cheap rule consistent with everything seen, which claims unobserved points of other classes. The 25.8-bit Draw rule is the type specimen.
Remedy: self-falsifying sampling. Query inside your own rules’ extensions. An accident contains its own counterexamples by definition, so it dies within a round or two; a correct rule is merely confirmed.
Recall — unseen fibers
Variants of a rare class lying outside every current rule: the X-centre draws, when only O-centre draws were ever shown. Self-falsification cannot find these — the model never claims them.
Remedy: discriminative queries. Sample where a rule disagrees with its own drop-one-atom generalisations — query-by-committee, where the committee is the certificate’s neighbourhood in the cost lattice.
Structure mismatch
The language cannot express the target cheaply at all — the cells-only row of the ablation.
No sampling policy fixes this. The learning curve is itself the diagnosis, and the only remedy is a richer type. Worth stating plainly: two of the three failure modes are the learner’s problem, and the third is the modeller’s.
Twelve rounds of queries, from a 200-label seed
target legal · held-out accuracy after each roundWhat the queries actually bought, in one pair of certificates
Both are seed 0, both end near 600–900 labels, both are two rules over a default. The difference is the OWon rule: purity queries confirm a narrow rule forever, because everything inside it really is an O-win. Only a query aimed at where the rule disagrees with its own cheaper generalisation produces the labels that let broaden take the bolder version.
START: everything -> Illegal [3.00 bits] OVERWRITE #X-#O=1 & N(0,3,0)=0 & N(3,0,0)>=1 -> XWon [36.95 bits, |S| = 626] OVERWRITE prof[col1]=(0,3,0) & #X-#O=0 & N(2,0,1)=1 -> OWon [35.20 bits, |S| = 36] TOTAL: 75.15 bits, 2 rules — 98.45%
START: everything -> Illegal [3.00 bits] OVERWRITE #X-#O=1 & N(0,3,0)=0 & N(3,0,0)>=1 -> XWon [36.95 bits, |S| = 626] OVERWRITE N(0,3,0)>=1 & #X-#O=0 & N(3,0,0)=0 -> OWon [36.95 bits, |S| = 316] TOTAL: 76.90 bits, 2 rules — 99.92%
| Protocol | Labels | Held-out accuracy | What is left wrong |
|---|---|---|---|
| IID | ~600 | 97.4–98.4% | Draw 11–16%; accidents still alive |
| IID | 1 183 | 99.85% | gets there eventually, at twice the labels |
| self-falsifying | 527–621 | 99.94% (2 of 3 seeds) | zero false positives; only the unseen draws wrong. Third seed 98.5% — a pure but narrow O rule, i.e. a recall failure |
| + discriminative | 788–1 183 | 99.91 / 99.92 / 100.00% | one seed exactly right; the Draw fiber still missed on two |
The limitation this exposed, stated by the authors
The drop-one-atom committee did not rescue the Draw fiber on two of three seeds. The true generalisation of the draw accident is a replace-variant — it swaps an atom rather than dropping one — and so lies outside the committee that was explored. The fix is to make the committee mirror the full move set of recompression (drop, replace, merge), which is one line per move. Reported as an open item rather than smoothed into the averages.
Phase II · a harder problem
Every hand in the deck, from 49 examples
Tic-tac-toe could be a lucky domain. Poker is a fair test of the same machinery at 132× the size: a type whose derived structure has three levels, ten classes spanning six orders of magnitude, and a rarest class with four members in 2 598 960.
Nothing about poker is supplied. The atom library is the same constructions as tic-tac-toe, applied to this type: multiplicities of the projection to Rank and to Suit; multiplicities of those multiplicities (N₁…N₄, which are the coordinates of the partition of 5); existential lifts (max rank multiplicity, max suit count); and, because Rank is ordered, windows of five consecutive ranks — which is where straights come from, ace high and low. 240 atoms after semantic dedupe.
Why the class counts matter
The first thing the run does is count its own classes: 1 302 540 high cards, 1 098 240 pairs, …, 4 royal flushes. Those numbers are in every combinatorics textbook, and they were not put in — they fall out of the type, the derived maps, and the target definition. Reproducing them exactly is a correctness check of the entire pipeline before a single thing is learned.
The panel below re-runs that check, and the whole certificate, on all 2 598 960 hands in your browser.
The learned certificate, verified against the entire deck
2 598 960 hands enumerated here, not looked up| # | Overwrite | Bits | |S| computed | |S| reported | Settles | Reads as |
|---|
“Settles” is how many hands each rule still owns once every later overwrite has painted over it. Bits are recomputed from the same choice-tree formula as the Python, not copied from the log.
It found cheaper predicates than the textbook
N₁=1 → TwoPair is not the definition of two pair. It is correct only because a Pair rule already fired: given “some rank repeats”, having exactly one singleton rank means {2,2,1}. Likewise N₁=0 → FullHouse after Trips. The overwrite order is doing real work — the same phenomenon as tic-tac-toe’s #Empty=0 → Draw.
Rarity is bought, not given
Straight flush costs 17.4 bits and royal flush 20.7 — the two most expensive rules in the certificate, for the two rarest classes. The cost model is paying for specificity in exactly the place a human would expect to, without being told that these are the “hard” hands.
And the same accident, in a new domain
The last rule is wrong. maxsuit≥3 & runtop=A means “three to a suit and an ace-high run”, not a royal flush. With four royal flushes in existence there is almost nothing to falsify it with — the identical rare-fiber economics as the tic-tac-toe draws, in a domain 132× larger.
Probe a hand
pick five cards — or take one of the presetsStructure derived from the type
Which overwrites fire, in order
The entire error budget is one rule
Phase II · the comparison everyone asks for
Six orders of magnitude of class imbalance, and what each method does about it
The baseline is the standard setup for this dataset: a 2×64 ReLU network on one-hot cards, Adam, class-weighted loss — 10 314 parameters against the certificate’s nine rules. Both are scored on every hand they were not trained on.
Per-class accuracy, against class size
rows ordered by how common the class is — 1 302 540 hands down to 4| Method | Train | Model size | Held-out | Rare classes |
|---|---|---|---|---|
| certificate poker | 49 | 126.9 bits | 100.000% | StraightFlush 87% — one accident |
| certificate poker | 184 | 126.9 bits | 99.984% | everything 100% except Straight 95.9% |
| certificate poker, unstratified | 1 000 | 76.8 bits | 99.974% | Quads, StraightFlush, Royal 0% — never appeared in the sample |
| MLP poker | 840 | 10 314 params ≈ 330 048 bits | 19.9% | — |
| MLP poker | 5 000 | 10 314 params | 64.6% | five classes at ≈ 0% |
| MLP poker | 25 000 | 10 314 params | 93.6% | FullHouse 3%, Quads 3%, StraightFlush and Royal 0% |
| certificate tic-tac-toe | 4 954 | 102.7 bits | 99.65% | Draw 0% — the 25.8-bit accident |
| MLP tic-tac-toe | 4 954 | 6 212 params ≈ 198 784 bits | 96.2% | XWon 62%, OWon 42%, Draw 0% — above the majority baseline overall, below it on every class that matters |
Where this wins, and why
When the target is exactly expressible in structure derivable from the input type — classification by symmetry, count and order invariants — the certificate learner wins by orders of magnitude on all three axes at once: data, model size, and interpretability. It is not close. Five examples per class is enough to write down the poker taxonomy, because the taxonomy is short in that language, and the search is looking for short things.
The second property is rarer and matters more: it degrades diagnosably. A certificate that bloats is telling you the language is wrong. A network at 93.6% with 0% on five classes is telling you nothing at all until you go looking.
Where it should be expected to lose
Stated by the authors rather than hedged: when the target is noisy, perceptual, or simply has no short structural description, gradient methods on flexible function classes keep the advantage. The cells-only ablation is the honest proxy for that regime, and there this method converges toward memorisation — which is at least a legible way to fail.
There is also nothing here about label noise: consistency is currently hard. The proposed frontier is the hybrid — type-derived features priced by description length as the hypothesis space, with statistical tolerance for noise — and it is first on the list of what to do next.
The honest part
Where it breaks: a 25.8-bit accident
On the legal target there are only 16 draws in 19 683 fields, and orbit sampling shows the learner just 4 of them. The cheapest rule consistent with those four is not the correct one. It is this:
“At least four lines with one X and two O’s, and at least three with two X’s and one O.” It is true of every draw it was shown, and of nothing else it was shown, so it is admissible, and it is cheap. It is also true of 44 fields in total, of which only the 4 observed draws are draws; it overwrites 16 genuine X-wins and relabels 24 illegal positions, and it misses all 12 draws it never saw. The correct rule (#Empty=0 & N₍₃,₀,₀₎=0 & N₍₀,₃,₀₎=0 & #X−#O=1) costs about 46 bits. With four examples, MDL is right to prefer the accident.
The accident’s extension, computed live
every field the rule fires onThe 44 fields it claims — coloured by what they actually are
The 16 real draws — how many does it catch?
This is a data-adequacy failure, not a coding leak
The distinction matters and the project makes it carefully. A coding leak would mean the language can compress arbitrary labellings, and the random control rules that out. What happened instead is that the observations do not yet falsify the cheap wrong rule. The prediction is quantitative: the accident should die when enough draws are seen that patching it costs more than the ~20-bit gap it enjoys.
The failure produced the missing move
An intermediate version made things worse when shown more draws: it stacked a second accidental Draw rule that overwrote 60 real X-wins, dropping XWon accuracy to 87.3%. Two accidents now cost more than one correct rule: the global optimum had flipped, but no local move could reach it. Repair proposes a rule for one point; broaden edits one rule. Nothing could propose one rule for two rules’ worth of responsibility. That gap is exactly the merge move, which was then implemented.
With merge, the same run gives 110.5 bits at 99.82% with X and O rules perfect, and the Draw rule becomes the partly-semantic cell(1,1)=O & #X−#Empty≥5 & N₍₃,₀,₀₎=0 — “full board, no X line, O in the centre”. Still an accident. Still, given the data, the right call.
Per-class accuracy across every configuration
| Target / sampling | Train n | Draws seen | Bits | Illegal | XWon | OWon | Draw | Overall |
|---|---|---|---|---|---|---|---|---|
| simple / orbit | 4 874 | 16 | 44.6 | 100% | 100% | 100% | 100% | 100.00% |
| simple / iid | 5 000 | 7 | 78.8 | 100% | 100% | 100% | 100% | 100.00% |
| legal / orbit | 4 954 | 4 | 102.7 | 99.83% | 96.60% | 100% | 0% | 99.65% |
| legal / iid | 5 000 | 1 | 100.9 | 99.99% | 100% | 100% | 20% | 99.91% |
| legal / orbit+rare (with merge) | 4 958 | 8 | 110.5 | 99.87% | 100% | 100% | 0% | 99.82% |
Note the trade in the last row: showing more draws makes the certificate more expensive and the X rule perfect. Accuracy on the rare class stays at zero because eight examples still are not enough to price the correct rule below the accident. That is the model working as specified, not an implementation bug.
Postscript: this failure now has a name and a remedy
Phase II separated it into precision, recall and structure mismatch. The Draw rule is a precision failure, and the remedy is to query inside it: an accident always contains its own counterexamples, so pointing the sampler at the learner’s own claims kills it in a round or two. That protocol reaches 99.94% from ~600 labels where IID sampling needs about twice as many.
The same shape reappeared in poker, in a domain 132× larger: one accidental rule for the rarest class, four examples of it in existence, and every error the certificate makes on all 2 598 960 hands traceable to that one rule. The pattern is not a tic-tac-toe artefact. It is what rare fibers cost.
Positioning
What the neighbours actually optimise
The survey holds one discriminator throughout: what is the primitive object each line of work minimises? That is the question that separates this construction from ordinary program synthesis, and it is the question the brief asked for.
| Field | Primitive object it optimises | Relation |
|---|---|---|
| MDL rule lists (Proença & van Leeuwen; RIPPER; CN2) | ordered (predicate, output) list, first-match-wins | Closest existing formalisation. A last-write-wins certificate is a decision list read backwards. But the subset language is arbitrary Boolean conjunctions over given attributes, with no type-derived structure, no symmetry pricing. |
| Kolmogorov structure function (Vereshchagin & Vitányi; Gács–Tromp–Vitányi) | two-part code: a set containing the data + the residual | The deepest formal ancestor of the trade-off. This project is an effective, finite, typed specialisation of it. The no-leakage requirement is exactly Kraft validity. |
| Stabilizer chains & canonical forms (Sims; McKay, nauty) | coset indices; canonical representatives | Structurally the closest match to the cost mechanism: coset indices are literally the “#choices” whose log is charged. The gap: that literature never treats them as description length inside a learning objective. |
| Program synthesis with library learning (DreamCoder, FlashFill) | a DSL program tree computing f(x) | Precisely the framing the brief ruled out. Nothing found in this cluster optimises edit sequences on an extension. |
| Version spaces (Mitchell; Hirsh) | the set of consistent hypotheses, via S/G boundaries | The classical analogue of “a correctly predicted example still shrinks the space”. Here the version space is not stored; it is an admissibility predicate derived from two bitmasks on demand. |
| Transformation monoids (Krohn–Rhodes; Even & Goldreich) | shortest generator word for a monoid element | κ(f) is a weighted word metric in the monoid generated by overwrites. No prior framing found of function complexity as shortest word from a constant function with bit-weighted generators. |
| Species & association schemes (Joyal; Bannai & Ito) | equivariant functors; orbit-defined relation algebras | The right language for the derived-map family, and it grounds “structure generates structure” as functor composition, but it supplied no mechanism the project didn’t already need. |
| Theory revision (FORTE; FRINGE; Wrobel) | a logical theory hill-climbed by typed edit operators | The closest behavioural match to incremental repair. Heuristic, no bit accounting, edits act on syntax rather than on semantically deduplicated subsets. |
Finding. No located prior work treats function complexity as weighted edit distance from a constant function, via edits on type-canonical structural subsets with explicit log₂(#choices) costing, combined with incremental MDL repair. The three nearest anchors above are each missing a different one of the three ingredients. The synthesis appears to be new, stated as a search result, with the searches listed, not as a claim of priority.
Limits
What is still wrong, in the author’s own account
Flat pricing is an upper bound
Choosing one cell of nine costs log₂9 regardless of how much symmetry remains. The intended scheme prices each choice by the alternatives inequivalent under the stabiliser of the choices already made — two-part orbit coding. A corner among the three cell-orbits: log₂3 + log₂4 ≈ 3.58 flat-priced at 3.17, but a corner followed by a symmetric continuation should cost only log₂3.
Flat pricing keeps the code prefix-free (Kraft mass ≤ 1 per family, tested), so nothing leaks. It just overprices highly symmetric subsets. Specified, not implemented.
Recompression is the bottleneck, and it knows it
Repair — the per-example step — is milliseconds even at 2 598 960 points. What costs is the global restructuring: broaden is O(rules × variants × rules) and merge O(rules² × search). The worst measured case is the no-lines ablation at n=4 000: 1 108 seconds for a 6 020-bit certificate, against 33 s for the 114-bit one on the same data.
Note what that means: learning time and certificate size fail together, and both point at the same cause — the language, not the algorithm. The implementation now caps broadening past 250 rules; the real fix is incremental recompression, and it is item 2 below.
The five experiments that would most reduce uncertainty
Revised after phase II — three of the original five were carried out, and what they turned up replaced them.
| # | Experiment | What it would settle |
|---|---|---|
| 1 | Noise tolerance — let a rule carry an exception budget priced at the extensional rate, and measure behaviour under label noise | The largest gap between this method and gradient learning. The mechanism already exists: overwriting a singleton is an exception. What is missing is letting the objective trade one rule against k patches, and then finding out whether it degrades gracefully. |
| 2 | Local recompression — after each repair, broaden and merge only the rules whose extensions intersect the new one | Removes the R² term that dominates every run above ~40 rules, and with it the 1 108-second worst case. |
| 3 | Stabiliser-refined pricing — the two-part orbit code with Schreier–Sims machinery | Carried over from phase I and still the most theory-relevant unknown. Prediction: general rules get relatively cheaper, so raw repair becomes less myopic and leans less on broadening. |
| 4 | A perception-adjacent domain — something MNIST-like with a known symmetry group | Maps the boundary with neural networks honestly, including where this method should lose. Everything measured so far is a domain where the truth is exactly expressible. |
| 5 | Deterministic multi-order canonicalisation — try a few structurally distinct canonical orders, not one | Closes the 76% → 96% gap of order invariance without giving up determinism. |
The method, stated as a method
The merge move was not designed in advance. It was found by localising a failure (a configuration where more data made the result worse), naming the move that was missing, implementing it, and re-running everything. The project recommends that loop explicitly, and item 1 above is the next place to point it. That is a more useful deliverable than any single number on this page.
Primary sources
Read the actual documents
Nothing here is a substitute for them. Everything on this page is drawn from these files.