The Optimal Choice of Hypothesis Is the Weakest, Not the Shortest

TL;DR

Everyone in machine learning has absorbed one rule of thumb: when two explanations fit the data, prefer the simpler (shorter) one. This is Occam’s Razor, formalized as Minimum Description Length (MDL), and it underpins the theory that “compression = intelligence.” This paper proves that idea is wrong — or at least neither necessary nor sufficient. It introduces a different property of a hypothesis called weakness: how many possible worlds a statement is still compatible with. The paper proves that to maximize the chance your inferred rule generalizes, you must pick the weakest rule that still fits your examples, and that no other selection rule can beat weakness across all tasks. In a toy binary-arithmetic experiment, choosing the weakest hypothesis generalized 1.1× to 5× more often than choosing the shortest. The practical takeaway for anyone building inductive systems: prefer the most general rule consistent with your data, not the most elegant one.

Problem & Motivation

Here is the concrete pain. You show a system a handful of examples (call them set A) and you want it to infer a rule that also handles the fuller reality it hasn’t seen yet (a superset B). Many different rules fit the examples in A. Most of them will be wrong about B. Which one do you pick?

The reigning answer, for 50 years, is “pick the shortest.” Rissanen’s MDL principle says shorter descriptions are simpler, and simpler tends to generalize. This is baked deep into the field:

• It is the working justification for regularization, for preferring small models, for “elegant” solutions.
• It is the theoretical foundation of Solomonoff induction and Hutter’s AIXI — the mathematical ideal of super-intelligence — which weight every hypothesis by 2^(−length), i.e. short programs are exponentially more likely.
• It fuels the popular claim that “the ability to compress is a proxy for intelligence” (Chaitin, Hutter, the Hutter Prize, and a lot of LLM-scaling rhetoric).

Bennett’s point: this proxy was adopted almost without challenge, and it’s the wrong one. Short and general are not the same thing. A short rule can be catastrophically over-committed (“all things are blue crabs” is short but wildly specific and wrong). The property that actually predicts generalization is how little a hypothesis rules out — and that is not length.

What’s New (Core Contribution)

Four things, precisely:

1. A new proxy — “weakness.” Before: generalization was proxied by description length (shorter = better). Now: it is proxied by the cardinality of a hypothesis’s extension — the number of possibilities it stays compatible with. Bigger extension = weaker = better. This is a measurable, well-defined quantity, not a vague appeal to “simplicity.”

2. A necessity-and-sufficiency proof. Before: MDL was a heuristic with intuitive backing. Now: the paper proves (under a uniform distribution over tasks) that maximizing weakness is both necessary and sufficient to maximize the probability that induction generalizes — and that MDL is neither. This is a Pareto/no-free-lunch style result: no proxy can do at least as well as weakness on every task while beating it on even one.

3. A computable “universal prior” built on weakness. Before: AIXI’s universal prior weights hypotheses by program length and is uncomputable. Now: weight each hypothesis h by 2^|extension(h)| / 2^|language|. Because the vocabulary is finite, this prior is actually computable, and it assigns “assume nothing” (the empty hypothesis) the highest prior — the honest default.

4. A reinterpretation of why DeepMind’s Apperception Engine works, plus a testable conjecture that LLMs hallucinate because they optimize loss, not weakness. Evans’ engine was explained via Kantian philosophy; Bennett gives a simpler reason — its universally-quantified rules are automatically weak. He proposes “Bennett’s Razor”: Explanations should be no more specific than necessary.

How It Works (Technically)

This is a theory paper, so the “mechanism” is a formalism plus two short proofs. I’ll build the vocabulary, then trace one concrete example all the way through, then demystify the two key equations.

The formalism in four objects

The paper models cognition “enactively” — as declarative programs that either accept or reject a state of the world. Four nested objects:

• State (φ) and declarative program (f). A state is one way reality could be (e.g. one specific 8-bit string). A declarative program is just a yes/no predicate over states: f: state → {true, false}. Think “bit 3 is 1.”
• Vocabulary (v) and statement (l). Pick a finite set of these predicates — that’s your vocabulary v. A statement l is a subset of predicates that can all be true at once (some state satisfies all of them). A statement is a logical formula: {bit0=1, bit3=1} means “bit0 is 1 AND bit3 is 1.” The set of all statements is the language Lv.
• Extension (Z) and weakness. The extension of a statement a is Za = {b : a ⊆ b} — every statement that includes a (i.e. every more-specific statement consistent with it). Crucial move: weakness of l = |Zl|, the size of its extension. Few predicates → many supersets → big extension → weak. The empty statement {} (assert nothing) is the weakest of all; a fully-specified statement is the strongest.
• Task. A task α = ⟨Sα, Dα, Mα⟩. Sα = situations (the inputs). Their combined extension ZSα = all possible decisions (candidate answers). Dα ⊆ decisions = the correct decisions. Mα = models: the statements h whose extension, intersected with the decision space, equals exactly the correct answers. A model is a hypothesis that nails the task.

Generalization is set up as child → parent. A child task α ⊏ ω has fewer situations than its parent ω (Sα ⊂ Sω) and a subset of the correct answers. You are given the child, not the parent. You compute the best hypothesis from the child and hope it is also a model of the parent. Induction = h = argmax over models-of-child of proxy(h); you win if h is also a model of the parent.

A concrete trace (the experiment’s setup, walked by hand)

Take 4 input bits + 4 output bits = an 8-bit string. The true rule is binary addition, so the parent task’s correct answers Dω are the 16 valid input→output rows. A situation is one of those rows with a single bit hidden (a 7-bit fragment). You want a rule that fills the hidden bit back in correctly for all 16 rows.

Now the catch: you only get a child task — a random sample of, say, 6 of those 16 rows. From those 6 you must infer a hypothesis (a propositional formula over the bits). Two candidate selection rules:

• Weakest (cw) — among all formulas consistent with the 6 rows, pick the one compatible with the most 8-bit strings (largest extension).
• Shortest / MDL (cmdl) — pick the shortest consistent formula.

Then reconstruct predictions for all 16 rows and check: did you recover the true addition table? The short formula can “explain” the 6 rows by latching onto an accident of those 6 (a compact but coincidental pattern) that breaks on the other 10. The weakest formula asserts the least beyond what the 6 rows force, so it stays compatible with the true remaining rows far more often. That is the whole idea.

Architecture & data flow

flowchart LR
  PHI[States Φ — every 8-bit string] --> P[Declarative programs — yes/no predicates]
  P --> V[Vocabulary v — chosen finite predicate set]
  V --> L[Language Lv — all satisfiable statements]
  L --> T[Task ⟨S, D, M⟩ — situations, correct decisions, models]
  T --> H[Hypothesis h = a model of the task]
  H -->|weakness = size of extension Zh| SEL[Selection proxy]

The hypothesis lattice (schematic, orbit to explore). Statements sit by specificity: weak/empty near the base with a large extension (many compatible worlds), specific statements near the top with tiny extensions. "Weakness" is literally how far down and wide a node sits. Generalization pulls you *down* the lattice, not toward the shortest label.

The two equations, demystified

Sufficiency (why weaker is better). The probability that a hypothesis h that fits the child also fits the unknown parent is:

p(h fits parent | h fits child) = 2^|Z̄Sα ∩ Zh|  /  2^|Z̄Sα|

Read it in plain English. Z̄Sα is the set of decisions that live outside the known child task — the unseen part of the world. Any subset of those unseen decisions could be the “extra correct answers” that a parent task adds, so there are 2^|Z̄Sα| possible parents out there (the denominator = all possible unseen worlds). Of those, the ones your hypothesis still gets right number 2^|Z̄Sα ∩ Zh| — the worlds that fall inside h’s extension. The ratio is the fraction of possible parents your hypothesis survives. The only lever you control is Zh: make the extension bigger (weaker hypothesis) and the numerator grows, so survival probability rises. Maximized exactly when |Zh| is maximal.

Necessity (why you have to use weakness). To be a model of the parent you need Dω ⊆ Zh — your hypothesis must permit every correct parent answer. If h’s extension is smaller than the parent’s answer set (|Zh| < |Dω|), it literally cannot contain them all and generalization is impossible. So a sufficiently weak hypothesis is a hard requirement, and the probability that |Zh| ≥ |Dω| is maximized by maximizing |Zh|. Hence weakness (or a function of it) is necessary.

The prior (the honest default). Absent any task, the chance a hypothesis generalizes to a random task is 2^|Zh| / 2^|Lv|, maximized by the empty hypothesis — “assume nothing.” That is a computable answer to the same question AIXI answers with an uncomputable, length-based prior.

Why this isn’t just Occam. Weakness is about extension (how much reality you stay compatible with), not form (how many symbols). A short statement can be very strong (tiny extension); a long statement can be very weak. They come apart. Proposition 3 gives an explicit counterexample where the shortest statement and the weakest statement are different, proving MDL doesn’t track weakness — and therefore doesn’t track generalization.

The algorithm, simplified

# Induction by weakness vs. by description length (one trial of the paper's experiment).
# A "decision" is a full 8-bit string. A "hypothesis" is a propositional formula whose
# extension is the set of 8-bit strings it accepts.

def extension(h, all_decisions):        # Zh: every world compatible with h
    return {d for d in all_decisions if h.accepts(d)}

def is_model(h, situations, correct):   # h in Mα: h nails exactly the correct decisions
    reachable = {d for s in situations for d in extension(h, all_decisions) if s.substr_of(d)}
    return reachable == correct

def induce(examples, candidates, all_decisions, proxy):
    # examples = the child task you actually see; candidates = consistent hypotheses
    consistent = [h for h in candidates if is_model(h, examples.S, examples.D)]
    if proxy == "weakness":
        return max(consistent, key=lambda h: len(extension(h, all_decisions)))  # weakest
    if proxy == "mdl":
        return min(consistent, key=lambda h: h.length)                          # shortest

def trial(parent_rows, k, all_decisions):
    child = sample_child(parent_rows, k)                 # you only see k of the rows
    cw   = induce(child, enumerate_hypotheses(child), all_decisions, "weakness")
    cmdl = induce(child, enumerate_hypotheses(child), all_decisions, "mdl")
    # generalized iff the hypothesis reconstructs the FULL parent table
    return reconstruct(cw, parent_rows) == parent_rows, \
           reconstruct(cmdl, parent_rows) == parent_rows

The one genuinely hard line is max(..., key=len(extension)): searching for the weakest consistent hypothesis is a combinatorial search, and counting extensions is expensive. The paper does it with A* search over propositional formulas, using SymPy for symbolic logic and PyTorch tensors for fast set operations on the bit-strings.

Why weak wins (interactive, schematic). Each cell is a possible answer; green cells are the parent's true answers `Dω`. Drag the slider to add constraints to your hypothesis — its extension `Zh` (blue) shrinks. A weak hypothesis (few constraints) still covers every green cell → it generalizes. Add too many constraints and `Zh` drops a green cell → generalization fails, even though the extra constraints made the formula "tighter."

Built on Prior Work

Results & Evidence

What was tested. A toy Python program (PyTorch + CUDA + SymPy + A*) on two 8-bit string-prediction tasks: 4-bit binary addition and multiplication. Each parent task has 16 valid rows; a child task samples |Dk| = 4–14 of them; for each child it builds the weakest model cw and the MDL model cmdl, reconstructs the full table, and checks against ground truth. 75–256 trials per setting.

Headline numbers.

| Task | |Dk| | Weakness gen. rate | MDL gen. rate | |---|---|---|---| | Addition | 6 | 0.11 | 0.10 | | Addition | 10 | 0.27 | 0.13 | | Addition | 14 | 0.68 | 0.24 | | Multiplication | 6 | 0.05 | 0.01 | | Multiplication | 10 | 0.16 | 0.08 | | Multiplication | 14 | 0.46 | 0.21 |

Across the board, weakness generalized at 110%–500% of MDL’s rate, and even when it didn’t fully generalize it recovered 103%–156% as much of the correct table. The gap widens as you get more examples.

The paper's measured generalization rates (weakness vs. MDL) for binary addition and multiplication as the number of visible examples grows. Weakness dominates at every point and pulls further ahead with more data.

What the evidence does and does not establish. It is a clean, controlled demonstration on a tiny, synthetic, fully-enumerable domain. It does not show weakness beats MDL on natural data, high-dimensional inputs, or real neural training — those are conjectures in the discussion, not results. The proof’s optimality claim rests on a uniform distribution over tasks (an idealization; real task distributions are not uniform — a tuned proxy can beat weakness on a cherry-picked subset, which the paper concedes). It also requires the finite-lattice formalism for weakness to be well-defined, and computing/searching the weakest hypothesis is expensive — its practicality at scale is unproven. The specific MDL baseline is one encoding; a different code could shift MDL’s numbers somewhat.

How You’d Use It

The grand AGI framing is optional. The usable nugget is a cheap, general selection heuristic for any component that infers a rule from examples: among the rules that fit, keep the one that commits to the least. Concretely for your work:

• Few-shot rule / schema / regex induction. When an agent infers an extraction pattern, a validation rule, or a mapping from a few labeled examples, rank candidates by generality (how many inputs they accept), not by brevity or “cleanliness.” The most general consistent rule is the safe bet on unseen records — exactly the failure mode where a slick, over-specific pattern silently misfires in production.
• Program-synthesis / config-inference features. If you offer clients “infer the transformation from these input/output pairs,” selecting the weakest consistent program is a principled default that reduces surprising over-fits.
• LLM prompting for rule extraction. The paper’s conjecture — models fabricate because they minimize loss, not weakness — has a direct prompt-level analogue: explicitly ask the model for the most general rule consistent with every example and to avoid asserting anything the examples don’t force. This nudges away from confident, over-specific hallucinations.
• Spec / guardrail inference in multi-agent systems. When one agent proposes a constraint another must satisfy, “weakest precondition that still fits the observed behavior” is a coordination-friendly default: it forbids the least and leaves the most room for downstream agents.

As a service offering, this is less a product than a quality lever you can apply across inductive components — a differentiator you can point to (“our rule-inference prefers the most general hypothesis, so it degrades gracefully on data it hasn’t seen”) rather than a standalone build.

Build Your Own (Minimal Recipe)

You can reproduce the core result in an afternoon, then lift the pattern into your stack.

1. Pick a tiny, fully-enumerable domain. 6–8 bit strings with a known rule (addition works). Enumerate all decisions all_decisions and the parent’s correct rows Dω.
2. Represent hypotheses as propositional formulas over the bits. Use SymPy for the logic; represent each formula’s extension as a boolean mask over all_decisions (a bit-vector / torch tensor) so intersection and counting are one vectorized op.
3. Define the two proxies. weakness(h) = mask(h).sum() (extension size). mdl(h) = -len(h) (shorter is better).
4. Search for the best consistent hypothesis under each proxy. For a toy domain, enumerate; for a bigger one, A* or a SAT/model-counting backend. The consistent set = formulas that reproduce exactly the child’s correct rows.
5. Sample child tasks, reconstruct, score. Sweep |Dk|, run many trials, compare full-table recovery rate for cw vs cmdl. You should see weakness pull ahead, widening with more examples.

The two hard parts: (a) searching for the weakest consistent hypothesis — it’s combinatorial; A* with an admissible heuristic on extension size is the paper’s answer. (b) counting extensions cheaply — exact counting is #P-hard in general, so beyond toy sizes you’ll need approximate model counting (sampling, or an ApproxMC-style counter). Libraries to reach for: SymPy (logic), PyTorch/NumPy (masked set ops), a SAT solver like python-sat, and an approximate model counter if you scale up.

How to Improve It

Five concrete, testable directions — the limitations are the leverage:

1. A weakness regularizer for neural nets. The paper conjectures LLMs hallucinate because they only minimize loss. Test it: add a differentiable surrogate for weakness (e.g. reward higher-entropy / less-committed decision sets consistent with the labels) and measure hallucination and grokking. This is the highest-upside, highest-risk direction.
2. Cheap weakness estimators. Exact extension counting doesn’t scale. Build and benchmark approximate counters (sampling, hashing-based ApproxMC, learned estimators) so weakness maximization can run on real problem sizes. Without this, the idea stays a toy.
3. Drop the uniform-task assumption. The optimality proof assumes tasks are uniformly distributed. Reweight weakness by a realistic task prior (empirical or learned) and check whether the advantage survives on natural data — where it matters commercially.
4. Learn the vocabulary v. The paper notes the Apperception Engine wins partly by a good choice of v. Weakness is defined relative to a vocabulary, so co-optimizing v and weakness (which predicates to even express rules in) is an open, high-value lever — get v wrong and no proxy helps.
5. LLM-agent implementation of “most general consistent rule.” Wire an agent that generates candidate rules from examples, estimates each rule’s generality (fraction of a held-out input space it accepts), and selects the weakest consistent one. Measure over-fit / hallucination reduction vs. a plain “infer the rule” baseline. This is the most directly shippable of the five.

Glossary

• Generalization — inferring from a small set A a hypothesis that also holds on a larger, unseen set B ⊃ A.
• Hypothesis / model — a logical statement that reproduces exactly the correct answers of a task.
• Extension (Zl) — the set of all possibilities (more-specific statements / worlds) a statement stays compatible with.
• Weakness (|Zl|) — the size of a hypothesis’s extension; how little it rules out. Bigger = weaker = more general.
• Description length / MDL — the length of a hypothesis; the classic “prefer shorter” proxy, formalized by Rissanen.
• Occam’s Razor — the heuristic that the simpler explanation is more likely; usually operationalized as “shorter.”
• Proxy for intelligence — a measurable quantity used to estimate which hypothesis will generalize.
• Enactive cognition — modeling a mind as programs that accept/reject states of the world, rather than symbols floating free of reality.
• Vocabulary (v) — the finite set of predicates you’re allowed to build statements from; weakness is defined relative to it.
• Child / parent task (α ⊏ ω) — a smaller task whose situations and correct answers are subsets of a larger one; you learn the child and hope to generalize to the parent.
• Universal prior — a probability assigned to every conceivable hypothesis before seeing data; AIXI’s is length-based and uncomputable, Bennett’s is extension-based and computable.
• AIXI — Hutter’s mathematical model of an optimal (but uncomputable) agent, built on Solomonoff’s length-weighted induction.
• Apperception Engine — DeepMind/Evans’ rule-inducing engine that generalizes well using universally-quantified logical rules.
• Bennett’s Razor — “Explanations should be no more specific than necessary.”
• Grokking — a training phenomenon where a network suddenly generalizes long after it has memorized the training data.