# Research memo: structural description complexity and incremental learning by extensional transformations *Deliverable F. Companion documents: `formalism.md` (the minimal formalism), `literature.md` (survey), `results/` (raw numbers). All numbers below are reproducible with the commands in `README.md`.* ## 0. Summary The proposed notion of complexity — minimum bit-cost of a sequence of overwrite transformations turning a constant function into `f`, with subsets specified through type-induced structure — was formalized with **three primitives** (structured domain, priced subset description, overwrite), implemented, and tested. The main findings: 1. **The unification works.** Point changes, orbit changes, multiplicity classes, and threshold regions are all fibers/regions of *derived maps* priced by one rule: every symmetry-breaking choice among `n` alternatives costs `log₂ n`. No separate primitives were needed, and the singleton emerged as the predicted degenerate case. 2. **Certificate search collapses to a shortest-path problem in a small lattice.** Because later overwrites win, minimizing a certificate is exactly a min-weight chain of "settled sets" — verified to coincide with brute-force shortest path over the full `|Y|^|X|` function graph. This is the useful discrete geometry the task asked about; the astronomically large Cayley graph of overwrites never has to be built. 3. **Incremental cheapest-repair works, but only together with structural recompression moves.** Raw repair is consistent and fast but myopic; with recompression (prune; replay; *broaden*: undo a symmetry-breaking choice, then re-specialize minimally; *merge*: one rule for several rules' responsibilities) it reaches the true optimum on 92% of all 256 functions of an exactly solvable domain, and on tic-tac-toe it recovers near-ideal certificates. 4. **Tic-tac-toe compresses as hoped.** From ~4950 of 19683 labeled fields the learner produces a **3-rule, 44.6-bit certificate with 100.00% accuracy on all 14809 unseen fields** for the task statement's target, and a 3-rule, 102.7-bit certificate at 99.65% for the stricter reachable-terminal target — whose X-rule covers *exactly* the 626 legal X-wins. Random labelings on the same domain stay incompressible (~0.9 bits/example, growing linearly) and generalize worse than the majority class. Memorizing the training labels would cost ~10000 bits. 5. **Two honest failures**: (a) rare classes (the 16 draws) attract "accidental" cheap predicates until enough of their orbits are observed to falsify them; studying this failure exposed a missing local move (*merge*), which was then implemented and measurably improved every configuration — but with 8 of 16 draws seen, the cheapest consistent Draw rule is still an accident, and MDL is right to pick it (§6); (b) the flat pricing of choices (`log₂ 9` for a cell, no residual-symmetry discount) is only an upper bound on the intended successive-symmetry-breaking cost; the refined scheme is specified but not implemented. ## 1. The cleanest abstraction found Everything reduced to one generative principle plus one transformation: > **A description is a walk through a prefix-free choice tree; its cost is the > sum of `log₂(#options)` over the choices made.** Structure enters solely by > *removing choices*: canonical constructions (counts, quotient profiles, > derived families like the 8 lines) are near-free because they are forced, > while every symmetry-breaking selection is paid for. A subset is the fiber > of a tupled derived map; the only transformation overwrites the function on > such a fiber. The type does real work. From `Field = Coor2 → Cell` with `Coor = {A,C}+{B}` the implementation *derives* — rather than postulates — the 9 evaluation maps, the global multiplicity space `Cell⁹/S₉` with its graded order and difference relations, the line family (fibers of the two projections plus graphs of `Aut(Coor)` — rows, columns, diagonals), line profiles in `Sym³(Cell)`, and the second-order multiplicities `N_p` = "number of lines with profile `p`". The mathematical language that fit best in practice was unglamorous: **graded multiplicity (count) spaces obtained by iterating two operations — restrict to a derived family, quotient by interchangeability** — i.e. symmetric powers used as functors, with association-scheme-like relations (equality, order, shifted diagonals) supplying the canonical regions. Species/configuration-space vocabulary describes this well but added no mechanism; nothing beyond "quotient, grade, iterate" was needed. ## 2. Concepts that turned out to be the same mechanism | apparent concept | what it actually is | |---|---| | change one point | overwrite on the fiber of the tupled evaluation map (most expensive instance) | | change one orbit / multiplicity class | overwrite on a fiber of a count map | | threshold region | up-set region of a *graded* count space (the order is part of the quotient, not an extra primitive) | | winning-line predicate | up-set `N_(3,0,0) ≥ 1` of a second-order count space | | "protected points" of the learner | the observation masks read through one admissibility predicate: `(S,y)` allowed iff every observed point in `S` has label `y` — derived on demand, never stored | | version space | the cone of admissible overwrites above the current settled chain; correct predictions shrink it without touching the extension | | certificate minimization | shortest weighted chain in the lattice of settled sets (ordered set cover); equivalently a decision list read in reverse | | the "broaden" search move | deleting one choice point from a description (∃-lift along a structural family), i.e. the cost model and the search moves are the same object | The last row deserves emphasis, because it was the key algorithmic discovery of the project: **the moves that repair a certificate are edits of the choice tree that prices it.** Adding an atom = making one more choice (specialize); removing an atom or replacing it by a broader one = undoing a choice (generalize, e.g. `prof[row1]=(3,0,0)` → `N_(3,0,0) ≥ 1` forgets *which* line was chosen). Search never manipulates syntax trees; it walks the cost structure itself, and semantically equal descriptions collapse because everything is memoized by extension (bitmask). ## 3. Where the unification failed or is incomplete - **The observation set stays extensional.** The hoped-for single object in which prediction, constraints, and allowed modifications all live was found only partially. The settled-set chain unifies the certificate with its own search space, and admissibility derives the version space from observations — but the observations themselves remain a plain partial function. The honest formulation: the learner state is a pair of partial functions of the same kind, one compressed (the certificate) and one extensional (the data); nothing in the formalism prevents compressing the second by the same machinery, but I did not find a way to *merge* them into one object without losing information about what was actually observed. - **Flat pricing.** Choosing 1 cell of 9 costs `log₂ 9` regardless of how much symmetry remains. The refined scheme — price each choice by the number of alternatives *inequivalent under the stabilizer of the choices made so far*, i.e. two-part orbit coding `L(S) ≈ log₂(#canonical forms) + log₂|orbit(S)|` — is strictly better when orbit sizes vary (a corner among the 3 cell-orbits {center, edge, corner}: `log₂ 3 + log₂ 4 ≈ 3.58` vs flat `log₂ 9 ≈ 3.17`; but "some corner, then a *symmetric* continuation" would 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. Not implemented; the most valuable next increment (§8). - **Replay recompression is engineering, not theory.** Prune and broaden are principled (remove a redundant rule; undo a choice point). Re-running the learner on a reordered observation stream is a heuristic restart. On the tiny domains replay contributes measurably, which signals that the local move set is still incomplete — an honest gap. - **Framing constants.** One bit per atom and per rule (continue/stop codes) is defensible but arbitrary at the ±1-bit level; conclusions are insensitive to it, but a fully principled treatment would derive framing from the choice tree too. - **Reuse discounts** (referencing an already-derived structure cheaply, DreamCoder-style library growth) are specified in the formalism but not implemented; single-function experiments gave them nothing to bite on. ## 4. Exact tiny experiments (deliverable C) Domain T1: `X = {a,b}^P`, `P` a bare 3-set (8 points, 2 outputs); domain T1′: same 8-point set but `P = bare-2 + bare-1` (the `Coor` shape, less symmetry). For **all 256 functions** the true optimum was computed by exhaustive settled-set Dijkstra over a semantically deduplicated library (validated against brute-force forward Dijkstra over all `2⁸` functions on a micro domain — costs agree exactly on all targets). From `results/tiny_results.json`: - Cost landscape on T1: min 2.0 (constants), median 19.75, max 28.34 bits. The 16 `S₃`-invariant functions average **11.4 bits** vs **20.3** for the rest. Named examples: majority 10.58; parity 19.17 (two `=`-fibers); the symmetric singleton `{aaa}` 10.58 (it is the count-fiber `#a=3`!); the asymmetric singleton `{aab}` 15.17 (`x[2]=b & #a=2` — successive refinement, exactly the predicted degeneration); worst function 28.34 ≈ extensional cost. Random functions are near the median — the language provably cannot compress them on average (prefix-free coding), and empirically does not. - **Structure dependence**: the same 256 extensions cost on average **+3.03 bits more on T1′** (158 costlier, 34 cheaper — cheaper is possible because T1′ also has *different* fibers, e.g. per-block counts; complexity is relative to the available structure, and structures are partially ordered, not linearly). - **Planted certificates**: for 200 random 2-rule certificates, the exact optimum is ≤ the planted cost in 100% of cases (sanity for optimality). ## 5. Incremental learner vs exact optimum (deliverable D) Same 256 functions, examples presented in random orders, full data: | learner | optimal (best of 10 orders) | mean ratio | worst | |---|---|---|---| | repair only | 43% | 1.105 | 2.24 | | + recompression (prune/replay/broaden/merge) | **92%** | **1.007** | 1.13 | | global greedy cover (cost/coverage) | 9% | 1.251 | 2.87 | | repair only, single order | 13% | 1.544 | 4.49 | | + recompression, single order | 60% | 1.056 | 1.61 | Observations: - **Repair is never inconsistent and never stuck** (universality: the singleton is always admissible), and its per-example work is a small local search: "cheapest admissible structural subset containing the wrong point". - **Myopia is real but cheap to fix.** The characteristic failure is tiling: a sequence of individually-cheapest medium subsets whose union should have been one general rule plus exceptions. Recompression repairs almost all of it; the residual gap (8% of functions even with the best of 10 orders, 40% for a single order) is order dependence. - **Global greedy is worse than incremental repair.** Cost-effectiveness greedy (pick the best cost/coverage rule for the *remaining* points) commits early to large rules that force expensive later patches. That the *incremental* algorithm with local moves beats the global greedy is evidence for the task's hypothesis that repair-based search is the right shape. ## 6. Tic-tac-toe (deliverable E) Setup: all 19683 fields; two targets — `simple` (the extension of the task statement's hand-written certificate) and `legal` (reachable-terminal classification; the implementation's count-based definition reproduces the known reachable-terminal counts **626 / 316 / 16** exactly, a nontrivial sanity check). Training: ~25% of fields, orbit-stratified (whole D4-orbits; 2862 orbits total) or IID; 523 atoms after semantic dedupe. Full log: `results/ttt_log.txt`, JSON: `results/ttt_results.json`. **Simple target, orbit sampling (4874 train / 14809 test):** 182 repairs during the pass; raw certificate 3214 bits (182 rules) → recompressed **44.6 bits, 3 rules, 100.00% test accuracy**: ``` START: everything -> Illegal OVERWRITE #Empty=0 -> Draw OVERWRITE N(0,3,0) >= 1 -> OWon OVERWRITE N(3,0,0) >= 1 -> XWon ``` This is *cheaper than the hand-written certificate in the task statement*: the learner discovered that under overwrite semantics "Draw" does not need a "no winning line" clause — later win-rules overwrite the wins out of the full-board region. Sequential overwriting is doing real compressive work (this is what makes the hypothesis class different from a conjunction-of- guards classifier). **Legal target, orbit sampling (4954 train / 14729 test):** 240 repairs; raw 5107 bits → **102.7 bits, 3 rules, 99.65%**: ``` START: everything -> Illegal OVERWRITE N(3,0,0)>=1 & #X-#O=1 & N(0,3,0)=0 -> XWon (|S| = 626) OVERWRITE N(0,3,0)>=1 & #X-#O=0 & N(3,0,0)=0 -> OWon (|S| = 316) OVERWRITE N(1,2,0)>=4 & N(2,1,0)>=3 -> Draw (|S| = 44) ``` The X and O rules are semantically exact (their extensions are precisely the legal win sets). The Draw rule is an **accidental predicate**: with only 4 draws observed, a 25.8-bit accident consistent with all 4954 observations beats the correct ~46-bit rule (`#Empty=0 & N_X=0 & N_O=0 & #X-#O=1`), and all 12 unseen draws are missed. This is exactly the failure mode the task statement warned about ("compression through obscure accidental predicates"), here confined to the class with 16 members. It is not a coding leak — it is a data-adequacy problem: the observations do not yet falsify the accident. With IID sampling (1 draw observed) the same story: 100.9 bits, 99.91% test, X and O rules perfect (100%/100%), draws wrong. The rare-class story also produced the sharpest algorithmic lesson of the project. In an intermediate version of the recompressor (prune/replay/broaden only), a rare-class-aware sampling variant ("orbit+rare": 75% of the orbits of any class with < 100 members, i.e. 8 of 16 draws observed) made things *worse*: the learner stacked a **second** accidental Draw rule (76 fields, overwriting 60 real X-wins; XWon dropped to 87.3%, total 128.3 bits), even though the two accidents together now cost more than one correct rule — the global optimum had flipped, but no local move could reach it: repair proposes the cheapest rule for *one point*, and broadening edits *one rule*. The missing move was a **merge**: replace several same-output rules by one rule found by the same search with "must contain a point" generalized to "must contain a set" (the union of the points those rules are responsible for). With merge implemented, orbit+rare yields 110.5 bits, 3 rules, 99.82%, X and O rules perfect again, and the Draw rule becomes the *partially semantic* `cell(1,1)=O & #X-#Empty>=5 & N(3,0,0)=0` — "full board, no X line, O in the center" — true on every observed draw orbit but still an accident that misses the unseen X-center draws (33.6 bits vs ≈ 49 for the fully correct rule; MDL is still right to prefer it given the data). The merge move also pushed `simple/iid` to a 3-rule, 78.8-bit certificate at **100.00%** test accuracy. **Controls (legal target):** | method | model bits | test accuracy | |---|---|---| | learned certificate | 102.7 | 99.65% | | memorize training labels | 9908 | — (predicts nothing off-train) | | majority class | ~2 | 95.12% | | 1-NN, Hamming on cells | (5000 rows) | 94.30% | | random-label control, n=250/500/1000 | 193/458/938 (≈0.8–0.9 bits/example, linear) | 86–88% vs 95% majority | The desired asymmetry is stark. The natural function costs ~0.02 bits/example, and the train-size sweep is a textbook MDL learning curve — certificate cost *rises toward the truth* as data falsifies cheaper wrong certificates while cost per example falls: | train n | cert bits | bits/example | test acc | |---|---|---|---| | 481 | 62.1 (3 rules) | 0.129 | 86.53% | | 989 | 88.0 (3 rules) | 0.089 | 98.67% | | 2457 | 101.1 (3 rules) | 0.041 | 99.79% | | 4954 | 102.7 (3 rules) | 0.021 | 99.65% | Random labels instead cost ~0.8–0.9 bits/example, grow linearly (193/458/938 bits at n=250/500/1000), and generalize *below* the majority baseline (86–88% vs 95%) because every accidental rule that fires off-sample is wrong. Note 1-NN — a reasonable conventional learner — is also worse than the majority class here (94.3% vs 95.1%): metric locality in cell space is the wrong bias for this function, while the structural bias is almost exactly right. ## 7. Did a useful discrete geometry emerge? Yes, and it is the settled-set lattice, not the naive function graph. The naive picture (functions as vertices, overwrites as weighted edges, κ(f) = distance from the constants) is correct — the tests confirm it exactly — but useless directly (`4^19683` vertices). The reduction shows the geometry that matters is the *lattice of unions of describable subsets*, whose chains are certificates. Three consequences: - κ(f) is a weighted word metric in a transformation monoid, but computable by Dijkstra over settled sets (exact for the tiny domains, where the whole reachable lattice has at most `2^|X|` and in practice a few hundred nodes). - Incremental repair is a *geodesic step in the admissible cone*: the new observation either lies on the current chain (no move) or forces the cheapest admissible extension of the chain through the new point. - "Functions related by a cheap structural transformation are close" becomes literal; and the broaden move shows the geometry is not just weighted but *stratified by symmetry* — moving to a coarser stratum (undoing a choice) is how compression happens. ## 8. What most reduces uncertainty next 1. **Stabilizer-refined pricing.** Implement the two-part orbit code (price choices by residual-stabilizer orbit counts; Schreier–Sims machinery is standard). Prediction: general rules get relatively cheaper than slice-rules, so raw repair should become less myopic and lean less on broadening. This is the single most theory-relevant unknown. (The analogous previous item — the merge move — was identified from the §6 failure, implemented during the project, and improved every configuration; that loop of "localize the failure of local search, name the missing move, add it" is itself the recommended method.) 2. **Exact optima at tic-tac-toe scale.** A* / branch-and-bound on the settled-set lattice with the 523-atom library, to measure the true gap of the incremental learner on the real domain (currently only bounded from one side: κ(legal) ≤ 102.7 bits given the library). 3. **Rare-class economics.** Vary draw coverage systematically and find the observation count at which the correct Draw rule overtakes accidents; compare with the ~20-bit cost gap the accident enjoys (a clean quantitative prediction of the MDL account: the accident should die when falsified or when its exception-patches cost more than 20 bits). 4. **A second type.** Run the identical pipeline on a different structured type (4×4 mis-de-symmetrized boards, or `Coor = {A,C}+{B}` replaced by a bare 3-set — which *changes* the derivable line family) to confirm the structure-dependence findings of §4 at scale. 5. **Reuse discounts / multi-function corpora**, where the certificate for one function makes structures cheap for the next (library learning at the level of derived maps, not programs). ## 9. Strongest connections to existing work See `literature.md` for the full survey (with the primitive-object comparison the task requested). The three nearest anchors: **MDL rule lists** (Proença & van Leeuwen) share the outer objective and the ordered-rule codelength, but over an attribute language with no type-derived structure or symmetry pricing; the **Kolmogorov structure function / algorithmic statistics** (Vereshchagin–Vitányi; Gács–Tromp–Vitányi) is the general theory of "cheap set containing the data vs residual", of which this project is an effective, finite, typed specialization; **stabilizer chains / canonical forms** (Sims; McKay) supply exactly the "choices under residual symmetry" that the cost model prices, though that literature never treats them as description-length in a learning objective. The specific synthesis — function complexity as weighted edit distance from a constant function, edits on type-canonical subsets, incremental MDL repair — appears to be novel; no close prior was found despite targeted search. ## 10. Answers to the twenty questions of `prompt.md` §16 1. *Minimal definition of a structured subset description?* A fiber/region of a map derived from the type by {evaluation, multiplicity quotient, fiber family, iteration}, priced as a prefix-free choice tree (`formalism.md` P2). Three constructors and one pricing rule. 2. *Can singleton/orbit/multiplicity/threshold selection be unified?* Yes — demonstrated in code: all four are atoms of the same kind, and the learner moves between them by adding/removing choice points (§2). 3. *What structures does the input type canonically induce?* Automorphisms; evaluation maps; graded multiplicity quotients at every level where positions are interchangeable; canonical sub-position families (fibers of projections, graphs of automorphisms); and the same again on every derived object (§1). 4. *How should higher-order structure be generated?* By iterating restriction and multiplicity-quotient on derived objects. `N_p` (multiplicities of line profiles) fell out mechanically and carried the entire tic-tac-toe solution. 5. *Natural description length of a subset?* Sum of `log₂(#options)` over the symmetry-breaking choices of its cheapest derivation, plus framing. Kraft validity is the correctness criterion (tested; and the random-function control is its empirical shadow). 6. *Related to residual symmetry?* In principle yes — the refined cost is `log₂(#orbits of continuations)` at each step under the stabilizer of choices made so far; implemented only in the flat upper-bound form (§3). 7. *One object for consistency + future transformations?* The pair (certificate chain, observed partial function) with the admissibility predicate; no third object is needed, but full unification into a single object was not achieved (§3). 8. *Is incremental repair shortest-path or refinement?* Both, literally: a repair is one edge of the settled-set shortest-path problem chosen inside the admissible cone; recompression is refinement of the chain (§7). 9. *What changes on a correctly predicted observation?* The admissible cone shrinks — some overwrites that were legal are no longer. The extension, the certificate, and the settled chain are untouched. 10. *Representable without per-point bookkeeping?* Yes: two bitmasks per class (observations), one admissibility test `S ∧ wrong(y) = ∅`. Nothing else is maintained (§2, table row 5). 11. *Can the cheapest consistent update be found locally?* Usually — the DFS over atoms containing the wrong point, with cost bound and stop-at-admissible, finds it in milliseconds at |X|=19683 (240 repairs in ~4 s). Universality guarantees it never fails outright. 12. *When does greedy repair fail?* When cheapest-containing-subset ≠ part of the cheapest certificate: characteristically *tiling* (many medium slices where one general rule + exceptions is cheaper) and *order traps* (an early cheap rule forces later expensive exceptions). Both are mostly repaired by prune/broaden; what remains needed replay, i.e. genuine global restructuring (§5). Frequency: ~40% of tiny functions need any recompression; ~8% (best-of-orders) are not fixed even then. 13. *Can descriptions be canonicalized to avoid enumerating equivalents?* Yes, semantically: everything is memoized by extension (bitmask), and the library keeps only the cheapest description per extension. This is memoization by denotation, not syntax (§2). 14. *Lower bounds on bits per new observation?* From prefix-freeness: a set of observations that distinguishes `2^k` admissible continuations forces ≥ k additional bits in the worst case; the random-label control realizes this (≈ constant bits/example, linear growth). A per-instance bound (which single observation forces how many bits) was not derived. 15. *Right account of the multiplicity spaces in `Field`?* Graded symmetric powers with their canonical order/adjacency (`m → m ± e_i`), iterated (profiles, then multiplicities of profiles); association-scheme-style canonical relations (equality, shift) on products of them. No heavier formalism earned its keep (§1). 16. *Does natural tic-tac-toe get a dramatically shorter description than random?* Yes: 44.6 bits (simple) / 102.7 bits (legal), constant in n, vs ~0.9 bits/example growing linearly for random labels — a ~40× per-example gap at n=1000, unbounded asymptotically (§6). 17. *Smooth convergence to extensional specification?* Yes: tiny-domain worst functions sit at extensional cost, and the asymmetric singleton is specified by successive refinement at full price; no cliff between "structured" and "unstructured" regimes (§4). 18. *Complexity as weighted distance from a constant function?* Yes — exact and validated; and the computationally meaningful geometry is the settled-set lattice, not the function graph (§7). 19. *Same mechanisms for compression and symmetry breaking?* Yes — that is the central identification: compression = choices *not* made; the search moves are edits of the choice tree; symmetry breaking is the unit of cost (§2). 20. *Closest literature?* MDL rule lists / Kolmogorov structure function / stabilizer chains; the synthesis appears novel (§9, `literature.md`).