Course / Act IV · The inferences Lecture 13

Induction at scale.

A handful of labelled objects and a rule that explains them — or several rules that explain them equally well. Induction is the inference that adds knowledge. Its engine is search; its honest output is a set of hypotheses, not a single truth.

~50 min read 4 worked examples 1 interactive lab Updated 2026-11-17

A parts inspector labels objects by four attributes. Six are labelled and two are not. The question is not “what is the label of this object?” It is “what is the rule?” — and the honest answer is a set of rules, not one.

00 / The hookThe rule behind the labels.

A conveyor-belt cell labels objects by four attributes — colour, shape, size, material — with a binary accept/reject label. Five objects are labelled; the rest are not. Infer the rule.

Table 0.1 · Six labelled objects and two unlabelled ones. The attributes are all you know; the label is what you want to predict.
ObjectColourShapeSizeMaterialLabel
c1redcubesmallmetalaccept
c2redcubelargerubberaccept
c3redcubelargemetalaccept
s1redspheresmallmetalreject
b1bluecubelargemetalreject
g1greencubelargerubber?
r1redcylindersmallrubber?
g2greencylindersmallmetalreject

Three rules fit the six labels: red and cube (rejects s1, b1, g2), red and (cube or cylinder) (accepts r1), and (red or green) and cube (accepts g1). All are consistent; they disagree on the unlabelled objects.

The examples do not identify a rule. They constrain a space of rules, and the space can be described exactly. That makes the inductive bias visible: the language decides what is expressible, the examples decide what survives.

The one idea

Induction is a search over discrete hypotheses, constrained by examples. The output is a hypothesis, not a truth. The set of hypotheses that survive is the version space, and it is the precise measure of what the examples leave open.

Induction as a search over a hypothesis space Examples enter a finite hypothesis space of rules. The rules consistent with the labels form the version space. A prior or cost chooses one rule from that set. c1 red cube + c2 red cube + c3 red cube + s1 red sphere − b1 blue cube − g1 green cube ? r1 red cyl. ? EXAMPLES HYPOTHESIS SPACE H · 441 RULES red ∧ cube red ∧ (cube ∨ cylinder) (red ∨ green) ∧ cube VERSION SPACE · 3 RULES red ∧ cube one rule, chosen by a prior SELECT
Fig. 0.1 A schematic, not a measurement. Examples filter a finite hypothesis space; the survivors are the version space; a prior selects one rule.

01 / Induction from examplesWhat follows from examples, and what does not.

Induction infers a rule that covers unseen cases. Peirce’s triad still locates it: deduction derives what must follow; abduction infers an explanation; induction infers a regularity. Deduction is truth-preserving; induction is ampliative — it goes beyond the premises, and its conclusion can be false. That is not a defect. It is the only way to add knowledge not already in the data.

Definition · induction as constrained search

Let H be a hypothesis space, B background knowledge, P positives, and N negatives. A hypothesis h ∈ H is consistent when it covers every positive and no negative. Induction searches for the consistent hypotheses, then chooses among them.

h* ∈ { h ∈ H :  ∀p ∈ P, B ∧ h ⊨ p   and   ∀n ∈ N, B ∧ h ⊭ n }
(1.1)

Induction is not statistical fitting

A neural network is also a hypothesis space and training is also constrained by data. The difference is the object returned. A parametric model returns weights and is judged by a loss. A rule or program learner returns a discrete object and is judged by coverage, entailment, or a checker. The object can be read and executed; the weights cannot, except through probes.

Table 1.1 · Two kinds of induction. Real systems sit between the columns; the table isolates the commitment each makes.
AspectStatistical fittingRule / program induction
HypothesisA parameter vector θ in a fixed architectureA discrete object h: a rule, a clause, a program
FitMinimize empirical risk, or a posteriorCover the positives; exclude the negatives; satisfy a specification
OutputWeights, scores, a decision boundaryAn inspectable artifact that can be executed or checked
GeneralizationSimilarity under the data distributionEntailment or execution on unseen inputs
Typical failureShortcuts, distribution shift, opacityWrong language, overgeneralization, combinatorial search

The trade: a strong language buys sample efficiency; a wrong language cannot be fixed by more data.

Generality, specificity, and the version space

Hypotheses are partially ordered by generality. With ext(h) the set of objects h covers, h1 is at least as general as h2 when it covers a superset:

h1 ≥H h2   ⇔   ext(h1) ⊇ ext(h2)
(1.2)

Mitchell’s version space is the set of consistent hypotheses. Its boundaries are the most specific consistent hypotheses, S, and the most general, G:

VSH,E = { h ∈ H : consistent(h, E) },    S = min≥ VS,   G = max≥ VS
(1.3)

Candidate elimination maintains the boundaries: a positive generalizes S; a negative specializes G. The two boundaries summarize the space, and the gap between them is where ambiguity lives.

A worked version space

Take the lab’s twelve objects. Label three red cubes positive and the red sphere, blue cube, and green cylinder negative. Each attribute may allow any non-empty subset of values; 7 × 7 × 3 × 3 = 441 rules.

The most specific rule is the least general generalization of the positives: all red and all cubes, with size and material unconstrained. So S = red ∧ cube.

To find the most general rules, relax S until a negative appears. Dropping colour admits b1; dropping shape admits s1; allowing all colours and shapes admits g2. Exactly two maximal relaxations remain.

Table 1.2 · The entire version space for the worked example. Three rules, two boundaries, and a precise account of the ambiguity.
RuleBoundaryCoversWhat it decides
colour = red ∧ shape = cubeSc1, c2, c3The safest rule; commits to both shared values.
colour = red ∧ shape ∈ {cube, cylinder}G1c1, c2, c3, r1Accepts red cylinders; rejects green objects.
colour ∈ {red, green} ∧ shape = cubeG2c1, c2, c3, g1Accepts green cubes; rejects cylinders.
The version-space lattice for the worked example The most specific rule, red and cube, sits at the bottom. Two most general rules sit above it: red and cube or cylinder, and red or green and cube. A dashed fourth rule, red or green and cube or cylinder, is excluded because it covers the green cylinder. S · red ∧ cube c1 c2 c3 red ∧ (cube ∨ cylinder) G1 · adds r1 (red ∨ green) ∧ cube G2 · adds g1 (red ∨ green) ∧ (cube ∨ cylinder) excluded: covers g2 (green cylinder) MORE SPECIFIC BELOW · MORE GENERAL ABOVE
Fig. 1.1 The version space of Table 1.2. The two general rules are incomparable; the dashed rule is excluded by the green cylinder.

Two unlabelled objects are ambiguous. r1 is covered by G1 but not G2; g1 is the reverse. Every other unlabelled object is rejected by all three rules.

The lab lets you relabel and watch the space shrink, split, or collapse. “Identifiable” adds negatives until S and G coincide. “No single rule” creates an empty version space; the greedy learner still finds two rules, because a disjunction is a different language.

Caveat · consistency is not truth

A rule in the version space is consistent with the examples, full stop. It is not more likely to be true without a prior, and it is not guaranteed to generalize unless the language contains the truth and the examples identify it.

Relational rules: inductive logic programming

Attribute-value rules treat an object as a vector. Most concepts are relational: a grandparent is an object connected to another through a parent. Program induction over relational data is inductive logic programming (ILP): the hypothesis is a logic program, the examples are ground atoms, and the background knowledge is a set of facts and rules.

Definition · ILP

Given background knowledge B, positives E+, and negatives E−, find a program H such that B ∧ H ⊨ e for every e ∈ E+ and B ∧ H ⊭ e for every e ∈ E−. The predicates, argument types, and recursion allowed in H are the language bias.

A small example. The background knowledge is a family tree:

parent(ali, reza). parent(reza, sara). parent(sara, omid). parent(ali, mina). parent(mina, omid).

The positives are grandparent(ali, sara) and grandparent(ali, omid); the negatives include grandparent(ali, reza) and grandparent(sara, omid). The learned clause is the obvious one:

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

The clause covers a ground atom when a substitution makes the head equal to the atom and every body literal true in B. For grandparent(ali, sara), X = ali, Y = reza, Z = sara works; for grandparent(ali, reza), no Y does. The shared Y expresses a relation between objects, not a property of one.

FOIL grows clauses top-down; Progol works bottom-up with inverse entailment; Metagol learns higher-order programs. All need a language bias, because the space of logic programs is too large to search. Background knowledge makes few-shot learning possible; the same bias makes consistency checking NP-hard.

02 / Programs and DSLsThe hypothesis is a program.

Program synthesis generalizes rule induction from clauses to programs. The specification can be input–output examples, a sketch with holes, a pre/postcondition pair, or a natural-language description. This lecture focuses on examples, because that is where the ambiguity is sharpest.

p* = argminp ∈ L(G) cost(p)   subject to   ∀(i, o) ∈ E: ⟦p⟧(i) = o
(2.1)

The grammar G defines the language L(G); the interpreter ⟦·⟧ defines the semantics; the cost function breaks ties. The grammar is not a detail. It is the hypothesis space, and therefore the inductive bias.

The DSL is the hypothesis space

A domain-specific language fixes the primitives, the types, and the composition rules. A small list DSL is enough to see the mechanics:

e ::= x | map(f, e) | filter(p, e) | reverse(e) | take(n, e) | drop(n, e) | sum(e) f ::= inc | double | neg p ::= even | positive

With this grammar, map(inc, x) is a program; map(inc, reverse(x)) is another. Types prune combinations: sum returns a number, so it cannot be an argument to map; filter expects a predicate. The grammar and type system are a strong prior.

Enumerative search, and why the smallest program wins

The simplest complete strategy is enumeration by size: test all programs of size 1, then size 2, and so on. Type-directed pruning removes ill-typed candidates; observational equivalence removes programs that behave identically; deduplication removes syntactic variants.

Suppose the examples are [1,2,3] → [2,3,4] and [10,20] → [11,21]. Among size-1 candidates, only map(inc) fits. The answer looks unique. It is not unique as a function: map(inc) and map(inc) ∘ reverse ∘ reverse agree on every list. Both are in the language if reverse is; the cost function prefers the shorter one. For [1,2,3] → 6 and [4,5] → 9, both sum and fold(add, 0) fit; the DSL’s order breaks the tie.

Table 2.1 · Three programs that fit the same two examples. Size counts primitives. The search returns the first by size; the others are equivalent on all inputs, or equivalent on the examples but not in general.
ProgramSizeFits the examples?Why it is not chosen
map(inc)1YesIt is chosen: smallest in the DSL.
map(inc) ∘ reverse ∘ reverse3YesExtensionally equal to map(inc); larger.
map(λx. x + 1 if x > 0 else x)—Yes, on positive inputsNot in the DSL; it differs on negative inputs.

The moral: “the program that fits the examples” is always relative to a language and a cost. The examples filter; the language and cost choose. Compositionality is what makes the choice useful — a program built from reusable parts can be recombined and checked.

Synthesis as a loop: propose, check, add a counterexample

Pure enumeration is fragile: a program can fit the examples and fail on the next input. Counterexample-guided inductive synthesis (CEGIS) closes the loop: a synthesizer proposes a program; a verifier checks it against the full specification; a counterexample is added to the examples; repeat. CEGIS also shows the limit. If the spec is a finite set of examples, “verified” means “fits the examples.” If it is a formal contract, verification can be sound, but writing the contract is the new bottleneck.

03 / Neural guidanceMake the search smaller, not the answer certain.

Enumeration by size is complete for a grammar, and hopeless for a realistic one. The number of programs grows exponentially; a DSL with a dozen primitives quickly outgrows any practical enumeration. The response is to learn a heuristic: a score that orders the search, or a policy that proposes the next step. The neural component does not replace the symbolic search. It makes it tractable.

DeepCoder: predict the primitives

DeepCoder (Balog et al., 2017) trains a network on a corpus of generated programs and their input–output examples. At test time, it predicts, for each primitive, how likely it is to appear in a solution, and the enumerator searches only over programs built from the top-k primitives. The score is a prior over the grammar:

search over { p ∈ L(G) : primitives(p) ⊆ topk(fθ(E)) }
(3.1)

The gain is real; so is the cost. The prediction inherits the corpus’s distribution. If the true program uses a primitive the network ranked low, the search cannot find it. A wrong prior turns a complete search into an incomplete one.

DreamCoder: grow the language

DreamCoder (Ellis et al., 2021) attacks the DSL itself. It alternates a wake phase, in which symbolic search solves tasks and writes programs, with a sleep phase, in which a recognition model proposes reusable abstractions and the library is refactored to compress the solutions. New abstractions join the DSL, so later searches can use them. A library is good when it makes the corpus of solved tasks shorter to describe.

This is library learning: it changes the hypothesis space rather than merely ordering it. The cost is compute and corpus dependence — the base DSL, the task distribution, and the refactoring heuristic all shape what can be discovered. Compression is a heuristic, not a proof.

LLMs as proposers

A large language model can propose a program, a clause, or a rule without a hand-built DSL. The useful pattern is not “ask for the answer.” It is propose, execute, check, repair: the model writes a candidate; an executor runs it; failures become feedback; the model revises. The checker is the arbiter.

Codex (Chen et al., 2021) generates Python functions from docstrings and is evaluated by unit tests. AlphaCode (Li et al., 2022) generates many candidates for competitive-programming problems and filters them with sample tests. FunSearch (Romera-Paredes et al., 2024) pairs an LLM with an evaluator in an evolutionary loop, using the LLM for variation and the evaluator for selection. In each case the guarantee is relative to the checker, and the checker is domain-specific.

The failure modes are familiar. The model can satisfy visible tests and fail hidden ones, exploit a weak evaluator, reproduce a benchmark it has seen, or produce a program that is correct on the examples but expresses the wrong rule — the ambiguity of Table 1.2, hidden inside a fluent answer.

Neural guidance of proof search

A neural theorem prover learns to select the next clause or tactic during backward chaining; the kernel checks the result. Rocktäschel and Riedel (2017) learn clause selection with differentiable backward chaining; GPT-f (Polu & Sutskever, 2020) proposes proof steps for a proof assistant. The guarantee is deductive; the guidance is learned.

Caveat · guidance is a prior, not a proof

A neural score can make the search faster and the result more plausible. It cannot make the result correct. If the checker is sound and the search is exhaustive over the guided space, the output is correct relative to the checker. If the guidance prunes the true program, the search is incomplete — and the system may not know it.

04 / Few-shot inductionExamples in the prompt, rules in the activations.

“Few-shot learning” names two things. In statistical learning it usually means meta-learning: training on many tasks so that a model can adapt from a small support set, often with a few gradient steps. In the language-model literature it means in-context learning: examples go in the prompt, the weights are frozen, and the model answers a new input.

Behaviourally, in-context learning is induction. The model sees red cube → accept, red sphere → reject, blue cube → reject, then a query green cube → ?. It answers. Change the examples and the answer changes; no parameter is updated.

What is the hypothesis? The model does not return one. The rule is implicit in the computation, and the only way to inspect it is to probe with more inputs. That is a real difference from the version-space learner, which returns the set of fitting rules. The in-context learner can be more flexible — natural-language concepts, background knowledge, patterns no DSL encoded — and less accountable: no boundary, no coverage set, no certificate.

What might be happening

Mechanistic work on controlled tasks has produced partial accounts. Garg et al. (2022) show that transformers trained on (x, f(x)) sequences can approximate simple function classes in-context, close to least squares on linear functions. Akyürek et al. (2022) and von Oswald et al. (2022) show that, under certain constructions, linear self-attention can implement steps of gradient descent or ridge regression. Olsson et al. (2022) identify induction heads that copy patterns from earlier in the context. Xie et al. (2022) model in-context learning as implicit Bayesian inference over latent concepts.

These are existence proofs on controlled problems, not an account of frontier models. They show that in-context learning is not one thing: retrieval, gradient-like adaptation, Bayesian updating, and copying can produce the same behavior.

Strengths, limits, and the neurosymbolic pattern

The strengths are obvious: no DSL, no grammar engineering, and the meaning of the prompt words is available. The limits are sharp. The rule is not inspectable, so it cannot be compared with a version space. Performance is sensitive to prompt order, formatting, and distractors. Compositional and length generalization remain fragile: SCAN (Lake & Baroni, 2018) showed failures on novel command combinations, COGS (Kim & Linzen, 2020) made the challenge explicit, and Dziri et al. (2023) show multi-step reasoning degrades with depth.

The neurosymbolic response is to ask for an artifact that can be checked. Instead of “what is the label?”, ask “write a predicate that agrees with these examples.” The model returns code; a harness runs it on the examples and held-out cases; a failure becomes a counterexample; the model revises. For the toy data, a plausible answer is:

def is_target(o): return o["colour"] == "red" and o["shape"] == "cube"

This is S, the most specific rule. It agrees with the six labels and rejects r1 and g1 — but G1 and G2 also agree and accept one of them. The model silently chose a point in the version space. If the task is to report what the data leave open, the code answers a different question. The fix is to ask for all consistent rules, a confidence, or a decision procedure that flags ambiguity — then check it against the examples. The checker still cannot tell you which rule is intended.

Table 4.1 · Three ways to induce a rule. They differ in what they return, what they can prove, and what they cost.
ApproachArtifact returnedAmbiguityGuaranteeCost
Version space / ILPAll consistent rules, or one clauseExplicit: S and GConsistency relative to HLanguage engineering; combinatorial search
Program synthesisA program in a DSLImplicit in the cost functionCorrect on the examples; verified if a checker existsDSL and search engineering
In-context LLMAn answer, sometimes codeNot representedEmpirical onlyPrompt design; no formal check

05 / What is learnedA program, a rule, or a representation.

“What did the model learn?” is not one question. The answer depends on the artifact the learner returns, and the artifact determines what can be inspected, transferred, and checked.

Table 5.1 · Three kinds of learned object. The same behavior can be supported by any of them; the differences appear when you try to inspect or reuse the result.
ArtifactExampleWhat it supportsHow to check itWhat it costs
A programmap(inc)Execution, composition, rewritingRun it on held-out inputsA DSL and a cost function
A rulegrandparent(X,Z) :- parent(X,Y), parent(Y,Z)Entailment, explanation, repairProve coverage in BA logic language and background knowledge
A representationAn embedding that makes a task linearly separableTransfer, similarity, downstream rulesProbe it; test it downstreamOpacity; many rules fit the same vector

The table warns against a common inference. A network that answers correctly may have learned a representation that supports the rule; it may also have learned a shortcut that correlates with it. A probe that finds a feature does not prove the model uses it. A program that fits the examples may be one of many equivalent programs. Behaviour underdetermines the hypothesis — the version-space ambiguity, moved into the learner.

Identifiability and the simplicity prior

To return one hypothesis, the learner needs a selection criterion. The most common is simplicity. The minimum description length principle makes it explicit:

h* = argminh ∈ H   L(h) + L(E | h)
(5.1)

L(h) is the description length of the hypothesis; L(E | h) is the cost of the examples given the hypothesis. Shorter rules are preferred because they compress the data. This is a prior, not a theorem. Kolmogorov complexity is uncomputable and depends on the universal machine; in practice the DSL supplies the code, and “shortest” means shortest in that DSL. Change the language and the preference changes.

The toy example shows the risk. red ∧ cube is shorter than (red ∨ green) ∧ cube, and both fit the labels. The shorter rule rejects the green cube g1; the longer one accepts it. If the intended rule is the longer one, the simplicity prior is wrong. The data cannot decide; only a prior or a new example can.

Representations are not rules

A representation encodes inputs so that a task becomes easy. A linear probe can recover a property from it; a concept bottleneck can force it to expose concepts. But a representation does not say which rule to apply. It supports many rules, and the choice is a separate hypothesis. “The model learned the concept” is usually a claim about a probe, not about the model’s computation. For a language model the artifact is even less tangible: the behavior is real, but the induced rule is not available for inspection.

06 / Guarantees and limitsWhat the induction actually buys.

The guarantees in this lecture are conditional, and it is worth stating the conditions precisely. Table 6.1 separates the claim from what it assumes.

Table 6.1 · Four guarantees and their assumptions. None of them says that the learned rule is the true rule.
ClaimWhat it guaranteesWhat it assumesWhat it does not say
Version-space consistencyEvery rule in VS covers all positives and no negativesH is fixed; labels are noise-freeThat the true rule is in H
Identifiability (S = G)All consistent rules agree on every objectThe boundaries coincide; the language is fixedThat the agreed rule is true
Synthesis correctnessThe program satisfies the specificationThe checker is sound; the search is complete over the guided spaceThat the specification captures the intent
PAC learningWith high probability, true error is within εFinite H; i.i.d. data; the target is in HAnything about a misspecified H

Sample complexity: the bias buys data

For a finite hypothesis class and the realizable case, the standard uniform-convergence bound is:

m ≥ (1/ε) ( ln|H| + ln(1/δ) )
(6.1)

With probability at least 1 − δ, every hypothesis in H with zero training error has true error at most ε, provided the sample is i.i.d. and the target is in H. The bound is loose, but the direction is right: a smaller space needs fewer examples. That is the formal version of “the bias buys data efficiency.” The catch is the last assumption. If the target is not in H, the bound says nothing, and no amount of data will fix it. A generalization gap can be a data problem or a language problem.

Noise, overgeneralization, and the empty version space

Real labels are noisy. Add one mislabelled object — say a green sphere is positive — and S becomes colour ∈ {red, green} ∧ shape ∈ {cube, sphere}, which covers the negative s1 (a red sphere). No consistent rule survives. The learner can enlarge the language, move from consistency to a scored rule, or treat the label as uncertain and collect more data.

Overfitting here has a precise shape: a rule more specific than the evidence warrants, or tuned to idiosyncrasies of the sample. The boundaries make it visible. A rule near S commits to every shared value; a rule near G ignores distinctions the data never tested. Neither is “the” answer; the choice is a bias–variance trade in a discrete space.

Ambiguity is the normal case

Examples rarely identify a unique rule. The worked example has three consistent rules from six labels; two more labels make S = G. In general, the version space shrinks only as fast as the examples constrain the language. More data can help; it can also reveal that the language cannot express the distinction you care about.

Goodman’s “grue” puzzle is the philosophical version: every emerald so far is green, and every emerald so far is also grue (green before a future time t, blue after). Both predicates fit; only a prior over predicates chooses. The version space is the formal shape of the problem, not a solution to it.

Computational limits and benchmarks

The search is expensive. Enumeration is exponential; deciding consistency of a logic program is NP-hard; neural guidance is incomplete in exchange for speed. “At scale” here means guided and checked, not complete and guaranteed.

Two limits are easy to miss. First, a finite specification is incomplete: a program can satisfy every example and fail on the next input. Second, benchmarks leak: a model may have seen the test set, a DSL may be tuned to the benchmark, and a “few-shot” task may be retrieval in disguise. An evaluation must say what the hypothesis space was, what the examples were, and what the checker could see.

The no-free-lunch caveat

Every induction result is relative to a bias. A bias that makes one task learnable makes another unlearnable. The useful question is not “which learner is best?” but “which hypothesis space contains the rule, and what does the evidence leave open inside it?”

07 / CasesFive systems, read along the same axes.

The cases below are chosen for mechanism, not for a leaderboard. Each answers the same questions: what is the hypothesis space, what guides the search, what checks the result, and what does the check assume?

Table 7.1 · Four rows, five systems. The guarantee column is the strongest claim the system can make, not the claim in its abstract.
SystemHypothesis spaceGuidanceCheckCaveat
FlashFillString-transformation DSLVersion-space search with rankingUser examplesIntent and ambiguity; domain-specific
DeepCoderList/arithmetic DSLNeural primitive predictionExamplesCorpus shift; top-k can exclude the truth
DreamCoderGrowing DSL with abstractionsRecognition model + compressionTask solutionsCompute; base DSL; corpus dependence
AlphaCode / FunSearchPrograms in a general languageLLM proposals + selectionTests or evaluatorReward hacking; leakage; evaluator cost

FlashFill: synthesis in a spreadsheet

FlashFill (Gulwani, 2011) synthesizes string transformations from one or two examples — splitting a name, reformatting a date. The hypothesis space is a DSL of string operations; the search is a version-space-style exploration with a ranking function. It shipped in Excel, which is strong evidence that inductive synthesis can be useful. The caveat is the specification: the examples are a tiny sample of the intent, and the ranking decides among the programs that fit.

DeepCoder and DreamCoder: two ways to scale

DeepCoder prunes the grammar with a learned prior over primitives. DreamCoder grows the grammar by learning abstractions. They are complementary answers to the same bottleneck: make the existing space smaller, or make it more expressive. Both depend on a corpus and a base DSL, and neither removes the checker.

AlphaCode and FunSearch: propose and test

AlphaCode generates many candidate programs for a problem statement and filters them with sample tests. FunSearch pairs an LLM with an evaluator and evolves a population of programs, using the evaluator to select mutations. In both, the LLM is a proposer and the checker is the guarantee. FunSearch is an existence proof that a guided program search can find constructions a human did not. The caveat is the evaluator: a program that scores well is not necessarily the program you wanted.

08 / RecapWhat you should be able to do now.

01

Distinguish induction of a rule or program from statistical fitting: a discrete hypothesis, a coverage test, an inspectable artifact.

02

Define the version space and its S and G boundaries; read ambiguity from the gap between them.

03

Explain what ILP adds: relations, variables, background knowledge, and a language bias.

04

Describe synthesis from examples: the DSL is the hypothesis space, the cost function the prior.

05

Explain how DeepCoder, DreamCoder, and LLM proposers guide search — and why guidance is not a guarantee.

06

State what a version space, a synthesized program, an ILP program, and a PAC bound each guarantee.

07

Name the normal failures: empty version space, overgeneralization, wrong language, leakage, and the specification gap.

Exercises

  1. Shrink the space. In the lab, start from the ambiguous preset and add labels until S = G. Which labels were necessary, and which were redundant?
  2. Break the language. Use the “No single rule” preset. Explain why no conjunctive rule covers both positives without a negative, and why the greedy learner still succeeds with two rules.
  3. Design a DSL. Choose a small string task. Write a grammar with five primitives, give two examples, and list every program of size ≤ 2 that fits. Which one would a shortest-program prior choose?
  4. Audit a few-shot answer. Ask a language model for a Python predicate that agrees with five examples. Test it on the unlabelled objects. Does it coincide with S, a G rule, or neither? What would you ask to recover the ambiguity?

Check your understanding

Ten questions, with explanations. The score is not the point; the questions you cannot answer are the reading list.

Reading list

The first three are the spine. The rest are the next layer: mechanisms, systems, and the limits.

Generalization as search

Mitchell · Artificial Intelligence 1982 · version spaces and candidate elimination

Foundations

Inductive logic programming at 30

Cropper, Dumančić, Evans & Muggleton · 2022 · the modern survey

ILP

Program Synthesis

Gulwani, Polozov & Singh · Foundations and Trends in Programming Languages 2017

Synthesis

DeepCoder: Learning to Write Programs

Balog et al. · ICLR 2017 · neural guidance of enumerative search

Guidance
Few-shot

Evaluating Large Language Models Trained on Code

Chen et al. · 2021 · Codex and execution-based evaluation

LLMs

Mathematical discoveries from program search with large language models

Romera-Paredes et al. · Nature 2024 · FunSearch

Search
Source note · what is verified and what is redrawn

arXiv identifiers and DOIs were checked against the arXiv API and Crossref. The datasets, tables, and figures are ours; the lab enumerates a hypothesis space defined on the page, not a result from a paper. No benchmark scores.