# When Compression Finds Programs That Generalize Discrete searches recover compact ownership, containment, XOR, and parity rules that generalize beyond training examples, while showing how strongly outcomes depend on a supplied grammar. Author: yoyo Publication date: 2026-10-18 Version: 1.0 ## Takeaway Compression-guided search found reusable rules for ownership, nested containment, XOR, and running parity, but the representation and program grammar were supplied in advance. ## The idea, in a minute ### The question Can a description-length objective select compact programs that generalize beyond observed examples, and what does that say about discovery versus assumptions built into the search space? ### What we found Across four small tasks, selected rules solved held-out cases including 1,000-bit parity strings and worlds with twenty nested containers. But the learner received task-specific representations, loops, memory, and operation vocabularies; the results demonstrate selection and generalization within constrained grammars, not open-ended invention. ### Why it matters The experiments make the inductive bias inspectable: a compact rule can extrapolate far beyond examples when its grammar contains the right mechanism. They also show that compression can prefer a short but under-supported shortcut. ### Keep in mind The code-length accounting is idealized and conditional on shared inputs, interpreter, and grammar. Grammar design is task-specific, and grammar cost is excluded, so compression ratios do not establish universal or raw-data compression. ## A concrete example: A loop beats three fixed links only because training leaves ambiguity The containment experiment trains on worlds with no more than one container, so both a three-link traversal and a membership-controlled loop fit the observed answers. ### Search The learner enumerates 370 update-and-traversal programs and scores them by program bits plus residual answer-label bits. ### Select The loop costs 60 model bits, compared with 80 bits for three fixed lookups, so it wins despite both matching the shallow training data. ### Test deeper On held-out worlds with five or twenty nested containers, the selected loop answers all 200 cases correctly; the fixed-depth rule answers none. The held-out test validates the coding prior’s choice in this task, while the ambiguity in training explains why that outcome is not a grammar-free discovery. Evidence: [Containment result record (in download archive)](/downloads/compression-discovers-generalizing-programs/evidence.zip) ## Reading the main result 0/200 to 200/200 — Unseen structure can separate fitting rules The containment loop and fixed three-link rule both fit shallow training, but only the selected loop generalizes to twenty nested containers. Hand-designed grammars, one principal seed for these subsets, repeated fixed challenges in sweeps, and idealized bit accounting. ## What this suggests - Small exact searches can recover mechanisms that extrapolate far beyond the observed examples when the grammar contains those mechanisms. - Counterexamples and held-out depth or sequence tests reveal when equally fitting short programs differ in generalization. ## What remains unknown - Whether one fixed grammar and code-length scheme can support multiple unrelated tasks without task-specific design. - How these methods behave when representations, interpreters, and grammars must themselves be learned. ## Abstract Can compression reveal a rule, or does it mostly reward rules we already made easy to express? These experiments give a concrete answer: small searches can find compact procedures that generalize dramatically, but only inside a supplied language of possible programs. The discovered rule may work on examples thousands of times longer than training, while the grammar still contains the loop, memory, or update mechanism that makes that result possible. Four experiments probe this boundary. Ownership examples select a last-matching transfer rule; containment examples select map updates plus unbounded traversal; Boolean synthesis reconstructs XOR from NOT, AND, and OR, then uses it for parity; and a separate sliding-window study learns numeric weights by direct matrix solves. The evidence is best read as a demonstration of constrained program selection and a guide to grammar design, rather than a claim of open-ended program invention. ## Research question Can a description-length objective select compact programs that generalize beyond observed examples, and what does that say about discovery versus assumptions built into the search space? ## Experiment setup The ownership learner receives an initial object-to-person map, ordered transfer triples, a query, and a person vocabulary. It searches 579 programs built from supplied register initializers, forward or reverse event scans, equality tests, assignments, and returns. The containment learner receives a map and normalized reparenting events; it searches 370 two-phase programs for event updates and traversal. Its event normalization is supplied, and physical reachability, permissions, parsing, and action preconditions are outside scope. The Boolean study first enumerates expressions from terminals and NOT/AND/OR, retaining minimum trees for each four-row truth table. XOR is absent as a primitive. It then selects a one-bit initial state and a fold update from 34 candidates. All binary strings of length zero through six form the 127 training examples. The separate sliding-window study fits a supplied quadratic feature map using incremental normal-equation summaries; it does not search for a program grammar. No experiment uses pretrained models, gradients, SAT solving, or external research. Detailed commands, code, result records, and tests are listed in the source manifest. ## Results For ownership, seed 7 selected a rule that initializes from the queried object’s current owner, then updates the register when the event names that object. It answered 200/200 new-name short worlds, 200/200 worlds with 10–20 transfers, and 200/200 100-transfer worlds. The ten-seed sweep selected the same program each time, with 6,050/6,050 evaluation answers correct; five fixed challenge cases repeat per seed. Training labels cost 43.33 ideal bits versus 320 literal bits. An insufficient-evidence set selected a shortcut that got only 2/5 challenge cases right. For containment, the selected program copies the map, applies each event as a parent update, then follows links until reaching a terminal node. It scored 200/200 at five and twenty unseen nested containers, while a three-lookup comparison scored 0/200 at both depths. The result achieved 67.91 ideal bits for seed 7 versus 480 literal label bits; seeds 0–9 selected the same program. However, training worlds allow at most three links, so a loop and a fixed chain both fit; the coding cost preferred the loop. For XOR synthesis, the minimum expression in the grammar was `(a OR b) AND NOT(a AND b)`, an eight-node exact fit to all four two-bit rows. The first task costs 24 ideal bits versus four literal labels, so it is not compression. For the parity fold, the selected 26-bit program had zero training errors, for a total of 33 program-plus-residual bits versus 127 literal bits. It got 8,064/8,064 strings of lengths 7–12, 1,000/1,000 random length-100 strings, 200/200 length-1,000 strings, and 42/42 fixed edge cases. Training only on the empty string and two one-bit strings instead favors constant zero and reaches 50% on the longer exhaustive suite. The numerical sliding-window companion is deliberately separate: with three supplied quadratic features, mean final MSE over seeds 0–19 was 0.072283 for window-only, 0.001833 with stability, 0.000174 with 30-example replay, and 0.000013 using all-history sufficient statistics. It shows that direct summaries can preserve old behavior in this fixed-feature problem, not that program search compressed neural learning. ## Discussion The central lesson is that generalization is jointly produced by evidence and the hypothesis language. In the containment case, a held-out depth test discriminates a loop from a fixed chain that training cannot distinguish. In parity, induction explains why the learned XOR update is correct at every length, but the fold and one-bit state were supplied. The one-example demonstration is equally informative: compression can select a short wrong rule when evidence does not justify a longer one. The code-length values are explicit modeling choices, not measured file sizes. They compress answer labels conditioned on shared inputs and interpreter, and omit the grammar’s own description cost. A future cross-task study should keep a common grammar and coding scheme fixed while broadening tasks, then account for the cost of the shared machinery. ## Limitations These are tiny, hand-designed search spaces and synthetic tasks. Ownership and containment inputs are structured records, not natural-language instructions. The Boolean training set is exhaustive only over short strings, and the data generator/interpreter are shared. Reported compression ratios are ideal description lengths, not compressed archives. The sliding-window result applies to a stable quadratic target with fixed features and low-dimensional direct solves. None of the experiments establishes scalable open-ended synthesis or transfer to arbitrary tasks. No trained-weight checkpoints apply: the outputs are selected symbolic programs or numerical trajectories, not neural model weights. ## Summary results | Condition | Held-out accuracy (%) | Program/code bits | | --- | --- | --- | | Ownership rule, 100 transfers | 100 | 36 | | Containment loop, 20 nested | 100 | 60 | | Containment fixed 3 links, 20 nested | 0 | 80 | | Parity, lengths 7–12 | 100 | 26 | | Parity, length 1,000 random | 100 | 26 | The chart reports exact held-out answers as a percentage for representative decisive contrasts. Ownership and containment are seed-7 test subsets; parity uses the listed held-out suite. These percentages do not share a common task distribution. ## Available materials The selected result JSON files contain programs, examples, score breakdowns, and numerical trajectories; they are not trained-weight checkpoints. This is standard-library research code. Source materials include only the four described studies and their focused tests. The evidence archive preserves selected reports and result records. Source paths and SHA-256 hashes are listed in provenance.json. This publication rechecked recorded outputs and archive integrity; no research experiment was rerun. ## References - [Ownership program search report (in download archive)](/downloads/compression-discovers-generalizing-programs/code.zip) - [Containment search and result report (in download archive)](/downloads/compression-discovers-generalizing-programs/code.zip) - [Boolean XOR and parity report (in download archive)](/downloads/compression-discovers-generalizing-programs/code.zip) - [Sliding-window weight learning report (in download archive)](/downloads/compression-discovers-generalizing-programs/code.zip)