# Research memo II: efficiency, order invariance, harder problems *Second research phase. Prior results and formalism: `memo.md`, `formalism.md`. Raw outputs: `results/curves_*`, `results/active_*`, `results/poker_*`, updated `results/tiny_results.json`.* ## 0. Summary of the second phase 1. **The learner is now an order-invariant function of the observation set**, with contradictions handled by an absorbing ⊥ state. Conceptually the observations live in a join-semilattice of partial functions; the batch learner composes a canonical linearization with the incremental machine, and deterministic recompression. The canonical batch learner is *better*, not just cleaner, than an average random presentation order. 2. **Sample efficiency tracks structural description length.** With full type structure, tic-tac-toe legality is learned to ~95% from 125 IID examples and ~99.9% from 4000; each ablation of type structure shifts the whole learning curve down and inflates certificates roughly in proportion to the extra bits the target costs in the impoverished language. 3. **The <100% failure mode decomposes into precision vs recall**, and the two respond to different remedies. Accidental predicates (precision) are eliminated by *self-falsifying sampling* — querying inside the learner's own rule extensions. Unseen variants of rare fibers (recall) additionally need *discriminative queries* — sampling where a rule disagrees with its own cheaper generalizations (query-by-committee over the cost lattice). More IID data fixes both, but orders of magnitude more slowly. 4. **A harder problem, and a direct NN comparison, both land decisively.** Poker hands (2,598,960 hands, 10 classes, worst class has 4 members): from **49 labeled examples** the learner writes a 9-rule, ~127-bit certificate that is the standard poker taxonomy and classifies all unseen hands at ~99.98–100%. A class-weighted MLP on identical data: 19.9%; on 25,000 random deals: 93.6% with 0% on five of the ten classes. On tic-tac-toe the same MLP gets 96.2% (Draw 0%, OWon 42%) where the certificate gets 99.65% at 1/2000 of the parameter bits. 5. **Time efficiency** is dominated by recompression, not repair: repairs are milliseconds even with |X| = 2.6M; broaden/merge scale ~(rules)² and are the practical bottleneck precisely when structure is too poor to compress (certificates with hundreds of rules), which is also when the method is telling you it has the wrong type. ## 1. Order invariance and the contradiction state The learner state was already the pair (certificate, observed partial function). The cleanup: observations form the join-semilattice of partial functions `X ⇀ Y` ordered by extension, completed with a top element ⊥. `observe(x,y)` is join with a one-point partial function; joining an incompatible point yields ⊥, which is absorbing — no certificate is consistent with ⊥ (the admissible cone is empty), so the learner reports contradiction rather than arbitrating (`test_contradiction_absorbing`). Order invariance is then obtained by making the certificate a *deterministic function of the semilattice element*: `learn_batch` sorts the set into a canonical order (largest class first, then class index, then point index), runs the incremental machine, and applies deterministic recompression (prune/broaden/merge, no randomized replays). Any permutation of the input yields the identical certificate (`test_batch_order_invariance`). Measured on all 256 functions of the exact tiny domain (true optima known): | learner | optimal | mean ratio | worst | |---|---|---|---| | single random order + recompression | 72.7% | 1.040 | 1.384 | | **canonical batch (deterministic)** | **75.8%** | 1.041 | 1.384 | | best of 10 random orders | 95.7% | 1.004 | 1.132 | The canonical order is a *good* order, not just a fixed one: it beats the average random order. The remaining gap to best-of-10 is the price of determinism; a canonicalization that searched a few structurally distinct orders (e.g. rarest-class-first as well) deterministically would close part of it. The incremental learner is unchanged and remains the anytime approximation: process points as they arrive, and the state converges to the batch answer whenever recompression is run. ## 2. Sample efficiency vs amount of type structure Target fixed (tic-tac-toe `legal`), IID samples, deterministic batch learner; atom libraries derived from progressively less of the type: held-out accuracy (mean over seeds; certificate bits at that n in parentheses): | n | full (523 atoms) | no-cmp (376) | no-lines (252) | cells (27) | |---|---|---|---|---| | 125 | 95.2% (58b) | 91.5% (77b) | 86.2% (104b) | 84.9% (120b) | | 250 | 97.4% (62b) | 91.4% (146b) | 89.6% (169b) | 87.1% (203b) | | 500 | 98.8% (102b) | 93.6% (284b) | 89.5% (400b) | 88.3% (581b) | | 1000 | 99.2% (123b) | 97.0% (348b) | 91.2% (726b) | 88.4% (1496b) | | 2000 | 99.7% (96b) | 98.7% (362b) | 93.1% (2001b) | 88.5% (2913b) | | 4000 | 99.9% (115b) | 99.5% (299b) | **90.8%** (6020b) | — | | 8000 | 99.9% (134b) | — | — | — | (majority-class baseline: 95.1%) Four readings: - **Curves order themselves by the target's description length in each language.** Certificate size at convergence tracks that cost (≈115 bits full, ≈300 no-cmp, thousands below), and accuracy at every n follows the same order. - **Full structure needs ~30–60× less data**: 95% at n=125 vs n≈4000+ for `no-lines`. - **`cells` plateaus at 88.4% — *below the majority baseline***, with certificates growing linearly in n (pure pattern memorization). A wrong language is worse than no language: every memorized pattern-rule overclaims off-sample. - **With poor structure, more data can hurt**: `no-lines` *drops* from 93.1% (n=2000) to 90.8% (n=4000) while its certificate quadruples — each new exception slice is another accidental predicate. Certificate bloat is the built-in diagnosis: the learner reports, in bits, that it has the wrong type. Efficiency is therefore not a property of the algorithm alone but of `κ_structure(target)` — the description length of the truth *in the available structure*. ## 3. Sample efficiency vs target complexity Structure fixed (full library), targets = planted random certificates of k rules (their planted cost is an upper bound on true complexity): | planted rules k | planted bits | recovered bits (n=4000) | acc @ n=250 | @ n=1000 | @ n=4000 | |---|---|---|---|---|---| | 1 | 17.2 | 17 | 100.0% | 100.0% | 100.0% | | 2 | 38.1 / 60.7 | 38 / 61 | 100.0 / 99.7% | 100.0 / 99.6% | 100.0% | | 4 | 99.5 / 112.6 | 86 / 65 | 99.3 / 99.9% | 99.6 / 100% | 99.8 / 100% | | 8 | 145.6 / 183.6 | 16 / 131 | 100.0 / 98.1% | 100.0 / 99.9% | 100.0 / 100% | | 16 | 373.5 / 335.5 | 151 / 2061* | 96.7 / 90.4% | 99.9 / 93.7% | 99.9 / 96.0% | (*the second k=16 draw is a genuinely hard extension: its recovered size is still growing at n=4000, i.e. the learner has not yet found a short description — and its learning curve is correspondingly the slowest of the grid, exactly the predicted coupling.) Two observations: - **Sample complexity scales with description length, as Occam predicts.** Using the recovered (large-n) bits as the complexity estimate, the error at n=250 rises monotonically with κ — 17 bits → 0%, ~60 → 0.3%, ~90 → 0.7%, ~130 → 1.9%, ~150 → 3.3%, ~2000 → 9.6% — consistent with err(n) ≈ c·κ/n, and all runs sit far inside the Occam bound (κ·ln2)/n. - **Planted cost is only an upper bound on true complexity, and the learner routinely beats it**: a 145.6-bit 8-rule plant was recovered at 16 bits — the later planted rules had overwritten most of the earlier ones, and the learner found the short description of the *extension* rather than the planting process. The right complexity measure of a function is κ of its extension, which is exactly what the formalism defines. Cheap targets snap in from tiny samples; expensive (near-random) targets degrade gracefully toward table-learning. As far as these experiments can resolve, the only property of the target that matters for sample efficiency is its description length in the structural language. ## 4. The <100% failure mode, and what fixes it The residual errors decompose into three distinct failure modes with different remedies: - **Precision failures (accidental predicates):** a cheap rule consistent with the sample claims unobserved points of other classes. Remedy: *self-falsifying sampling* — the learner queries inside its own rules' extensions. Every accident contains its own counterexamples by definition, so it is falsified within a round or two; correct rules are merely confirmed. - **Recall failures (unseen rare fibers):** variants of a rare class outside every current rule (the X-center draws when only O-center draws were seen). Self-falsification cannot find these — the model never claims them. Remedy: *discriminative queries* — sample where a rule disagrees with its own drop-one-atom generalizations. If the bolder rule is true, the labels let broaden/merge adopt it; if false, it is refuted once instead of remaining forever untested. (This is query-by-committee where the committee is the certificate's neighborhood in the cost lattice.) - **Structure-mismatch failures:** the language cannot express the target cheaply at all (§2 `cells` row). No sampling policy fixes this; the learning curve itself is the diagnosis, and the remedy is a richer type. Measured (tic-tac-toe `legal`, seed 200 IID labels, then 12 rounds of queries): | protocol | labels | held-out accuracy | |---|---|---| | IID | ~600 | 97.4–98.4% (Draw 11–16%) | | IID | 1183 | 99.85% | | self-falsifying | 527–621 | **99.94%** on 2/3 seeds (only the unseen draws wrong); 98.5% on the third | | + discriminative | 788–1183 | 99.91% / 99.92% / **100.00%** | Details that matter: - Self-falsification converges to the exact X and O rules and *zero* false positives with ~600 labels — every accident it ever proposed was refuted by its own queries within a round or two. Its one residual failure (seed 0: a pure-but-narrow OWon rule covering 36 of 316 O-wins) is precisely a recall failure: purity queries confirm a narrow rule forever. - The discriminative mode fixed exactly that case — querying where the rule disagrees with its drop-one-atom generalization produced the labels that let broaden adopt the full 316-point O rule — and one seed reached a perfect 100.00%. - Honest limitation: the drop-one-atom committee did *not* rescue the Draw fiber in 2 of 3 seeds. The true generalization of the draw accident (`cell(1,1)=O & ... → #X-#O=1 & ...`) is a *replace*-variant, outside the committee explored. The committee must mirror the full move set of recompression (drop, replace, merge), a one-line-per-move extension. Rebalancing the dataset across *the true function's* fibers (orbit- or class-stratified sampling) helps recall but cannot be planned in advance for unknown targets; the active protocols are the learnable version of the same idea — rebalancing across the *hypothesis's* fibers, which are known. (The construction is query-by-committee — Seung, Opper & Sompolinsky, COLT 1992 — with the committee generated structurally: the certificate's neighbors in the cost lattice.) ## 5. A harder problem, and the neural-network comparison **Poker hands.** Type: `Hand = Sym^5(Rank × Suit)` with `Rank` ordered, `Suit` bare. |X| = 2,598,960; 10 classes; class sizes from 1,302,540 down to 4. The derived structure is the same constructions as tic-tac-toe: rank and suit multiplicities (first order), multiplicities of multiplicities N_k (second order — the coordinates of the partition of 5), existential lifts (max mult, max suit count), and the run family from the *order* on Rank (windows of 5 consecutive ranks, ace both high and low). 240 atoms after semantic dedupe; the computed class counts match the combinatorial literature exactly (a nontrivial correctness check of the whole pipeline). Certificate learner vs MLP (2×64 ReLU, one-hot 85 inputs, Adam, class-weighted loss — the standard UCI poker-hand setup), all evaluated on every hand not in training: | method | train examples | model size | held-out accuracy | rare classes | |---|---|---|---|---| | certificate | 49 (5/class) | **126.9 bits** (9 rules) | **~100.000%** | StraightFlush 87% (one accident) | | certificate | 184 (20/class) | 126.9 bits (9 rules) | 99.984% | all 100% except Straight 95.9% | | certificate | 1000 random deals | 76.8 bits (6 rules) | 99.974% | unseen classes (Quads, SF, Royal) 0% | | MLP | 840 (100/class) | 10,314 params (~330k bits) | 19.9% | — | | MLP | 5,000 random | 10,314 params | 64.6% | 5 classes ≈ 0% | | MLP | 25,000 random | 10,314 params | 93.6% | Straight 24%, FullHouse 3%, Quads 3%, SF and Royal 0% | The stratified-20 certificate is worth quoting in full because it *is* the poker taxonomy, discovered from 184 examples: ``` START: everything -> HighCard maxmult>=2 -> Pair N1=1 -> TwoPair (exactly one singleton rank = {2,2,1}) maxmult>=3 -> Trips straight -> Straight maxsuit=5 -> Flush N1=0 -> FullHouse (no singleton rank = {3,2}) maxmult=4 -> Quads straight & maxsuit=5 -> StraightFlush maxsuit>=3 & runtop=A -> RoyalFlush (the one accidental rule, 20.7 bits) TOTAL: 126.9 bits ``` Note the two-pair and full-house encodings: the learner found *cheaper* correct predicates than the textbook ones by exploiting overwrite order (N1=1 under an earlier Pair rule; N1=0 after Trips), the same phenomenon as tic-tac-toe's `#Empty=0 -> Draw`. The one accident (`maxsuit>=3 & runtop=A`, which overclaims 420 ace-high straights) is again a rare-fiber economy: with 4 royal flushes in the world there is very little data to falsify with — and it is exactly the kind of rule the discriminative queries of §4 remove. On tic-tac-toe `legal` (same orbit-25% split as the main experiment) the MLP reaches 96.2% overall but 62% on XWon, 42% on OWon, 0% on Draw — worse than the majority baseline on the classes that matter — against the certificate's 99.65% at 102.7 bits vs ~199k bits of parameters. **When can this compete with neural networks?** The fair statement from these experiments: when the target is (near-)exactly expressible in structure derivable from the input type — classification by symmetry-, count-, and order-invariants — the certificate learner dominates by orders of magnitude in sample efficiency, model size, and interpretability, and degrades *diagnosably* (its certificate bloat tells you the language is wrong) rather than silently. When the target is noisy, perceptual, or has no short structural description (the `cells` ablation is a proxy), gradient methods on flexible function classes keep an advantage; the certificate learner's honest behavior there is convergence toward memorization. The interesting frontier is hybrid: type-derived features priced by description length as the hypothesis space, with statistical tolerance for noise (§7 next steps). ## 6. Time efficiency and scaling Measured costs (single core, pure Python + numpy masks): - **Repair** (the per-example step) is fast and scales with the atom count and |X|/64 words per mask AND: milliseconds on |X| = 19,683 with 523 atoms; ~0.1–0.3 s on |X| = 2,598,960 with 240 atoms. Learning tic-tac-toe from 4954 examples: ~4 s of repairs (240 of them; correctly predicted examples cost ~µs). Poker from 49 examples: 11 s end-to-end. - **Recompression** dominates: broaden is O(rules × variants × rules) and merge O(rules² × search); ~15–40 s at 40–60 rules, and it is what blows up when structure is poor: the worst measured case is `no-lines` at n=4000 — a 6000-bit certificate taking 1108 s, vs 33 s for the full-structure 114-bit one at the same n. Learning time and certificate size fail *together*, and both point at the same cause (the language, not the algorithm). Since certificates that large mean the language is failing anyway (§2), the implementation now skips broadening beyond 250 rules; the deeper fix is incremental recompression (recompress only the neighborhood a repair touched). - **Memory** is one bitmask per atom (|X|/8 bytes): 1.3 MB for tic-tac-toe, 78 MB for poker. Everything ran in <1 GB RAM. The asymmetry — cheap repairs, expensive global moves — supports the original architectural hypothesis: incremental repair is the right inner loop, and global restructuring is an occasional, bounded event. ## 7. Answers to the practical questions posed for this phase 1. **How efficient is learning in time?** Seconds to tens of seconds per dataset at these scales; bottleneck is recompression, not data ingestion; see §6. 2. **In dataset size?** Governed by the target's description length in the available structure: ~125 examples for 95% on tic-tac-toe legality, 49 examples for ~100% on poker, and provably-degrading-to-table-size for structureless targets (§2, §3). 3. **Dependence on the typing?** Monotone and large: each removed structure family shifts the learning curve by roughly the factor its atoms save in the target's description (§2). The formalism makes this quantitative: predict the curve from κ in each language. 4. **Dependence on the true function?** Through κ(f) only, as far as these experiments can resolve (§3). 5. **More complicated problems?** Poker (|X| 130× larger, 10 classes, 3-level structure) worked without any new mechanism (§5). The scaling limits are the explicit-bitmask representation (fix: lazy/sampled extensions) and recompression cost (fix: local recompression). 6. **Compete with neural networks?** Yes, decisively, on structure-exact targets; no, presumably, on noisy/perceptual ones; see §5 for the boundary and the hybrid direction. 7. **The 92%-not-100% failure mode?** It is not one mode but three (precision / recall / structure mismatch), each with a distinct, testable remedy; more data or fiber rebalancing fixes the first two slowly, active self-falsification + discriminative queries fix them fast, nothing but a better type fixes the third (§4). 8. **Order invariance and contradictions?** Done, and it made the learner both cleaner and slightly better (§1). ## 8. What would most reduce uncertainty next 1. **Noise tolerance**: replace hard consistency with a per-rule exception budget priced at the extensional rate (an overwrite of a singleton is already the natural exception mechanism — the missing piece is letting the *objective* trade one rule against k singleton patches, which it already can, and measuring behavior under label noise). 2. **Local (incremental) recompression** to remove the R² bottleneck: after each repair, broaden/merge only rules whose masks intersect the new one. 3. **Stabilizer-refined pricing** (carried over from phase I, still the most theory-relevant unknown). 4. **A perception-adjacent domain** (e.g. MNIST-like with a known symmetry group) to map the boundary with NNs honestly, including where the method should lose. 5. **Deterministic multi-order canonicalization** to close the 76%→96% gap of §1 without giving up order invariance.