Lecture 10 · Logic as search

Logic as search.

A specification is a few examples. A program is a term in a grammar. The task is to find the term — and to know what the finding guarantees.

4 search problems 5 case systems 1 pruning toggle Self-paced
00 · Learning objectivesLecture 10 · Logic as search

By the end of this lecture

Four things you can do.

01

Read the search space

Name the DSL, the cost, the examples, and the bound — and estimate what the space costs.

02

Separate deduction from induction

Say which approach is correct by construction, which is consistent with a sample, and why.

03

Search for a proof

Explain resolution, unification, and why a found proof is checkable while a timeout is not a disproof.

04

Guide search honestly

Distinguish ordering, pruning, and proposal-plus-check — and say which keeps the guarantee.

S/V · Lecture 10
00 · The hookLecture 10 · Logic as search

A specification a child can read

Three examples. One program.

InputOutput
[1,2,3,4][3,5,7,9]
[0,1,2][1,3,5]
[2,3][5,7]

The DSL: reverse · sort · take(k) · drop(k) · map(f) · filter(p) · count(p) · sum · length · pipe(f,g)

CandidateFirst output
map(+1)[2,3,4,5]✗
map(×2)[2,4,6,8]✗
filter(even)[2,4]✗
pipe(map(×2), map(+1))[3,5,7,9]✓

The answer is a term, not a weight. Three examples, three exact checks. No gradient in sight.

S/V · Lecture 10
00 · The hookLecture 10 · Logic as search

Why this is not learning

Language, cost, search.

Language

What programs are expressible. A DSL with types and arities. The lookup table is excluded here — and that exclusion is the generalization.

Cost

Which consistent program wins. Constructors, characters, or a prior. The first program is the simplest under your cost, not the intended function.

Search

How to find one without enumerating everything. Types prune, costs order, examples cut, and a learned score decides where to look.

Examples are the specification. Language and cost are the bias. The search is the algorithm. The checker is the only part that can say the answer is right.
S/V · Lecture 10
01 · The search spaceLecture 10 · Logic as search
01 / 08

A grammar, a cost, a search.

The space is not given. You build it, and the build decides what can be found.

S/V · Lecture 10
01 · The search spaceLecture 10 · Logic as search

The hypothesis space

A grammar is a hypothesis space.

Programs are typed terms. A constructor has an arity and a type; a term is well typed or it is not. map wants an element function, filter wants a predicate, pipe wants two list functions.

Cost is a choice. Every constructor costs 1; map(f) costs 1 + cost(f); pipe(f,g) costs 1 + cost(f) + cost(g).

p* = argmin c(p) subject to ⟦p⟧(xᵢ) = yᵢ for every example.
TermType
reverse, sort, tail, take(k), drop(k)list → list
map(f)(int→int) → list→list
filter(p)(int→bool) → list→list
count(p)(int→bool) → list→int
sum, length, max, firstlist → int
pipe(f,g)list→list, then list→T
+1, ×2, −x / even, odd, >0int→int / int→bool

A different DSL is a different hypothesis space, even with the same examples.

S/V · Lecture 10
01 · The search spaceLecture 10 · Logic as search

Enumeration by cost

Count the space before you search it.

With b atoms, u unary and q binary constructors, depth h has roughly N(h) = b + u·N(h−1) + q·N(h−1)² programs.

BoundWell typedNo type check
cost 44867,801
cost 53,10381,563

The lab's counts, exact for this grammar.

16× at cost 4. 26× at cost 5. That is the value of a type discipline, measured in candidates that never need to be evaluated.

The first consistent program is cost-minimal. A heuristic can find one sooner; it cannot find a cheaper one.

b = 10, u = 10, q = 5: 610 at depth 1, 1,866,610 at depth 2, trillions at depth 3.

S/V · Lecture 10
01 · The search spaceLecture 10 · Logic as search

Remove before you check

Three prunings, three guarantees.

Type / arity

Sound by construction. An ill-typed term has no value, so it cannot be consistent. Removing it cannot lose a solution.

Behavioural dedup

Sound for the probes. Two terms that agree on the example inputs and the fixed probes are kept as one. They may differ elsewhere.

Learned score

Not sound. A confident model can prune the only path to the answer. This is the completeness cost of neural guidance.

Pruning changes the cost, not the answer — if the pruning is sound. The default preset expands 1,041 candidates with types, 53,083 without, and finds the same program.
S/V · Lecture 10
02 · Deductive synthesisLecture 10 · Logic as search
02 / 08

Correct by construction.

Deduction starts from a specification and extracts a witness. Induction starts from examples and hopes.

S/V · Lecture 10
02 · Deductive synthesisLecture 10 · Logic as search

Manna & Waldinger, 1980

Prove it, then extract it.

The synthesis problem is a theorem: ∃f. ∀x. φ(x, f(x)). A constructive proof gives a term for f. That term is the program; the proof is the search.

1 · Specification

∀xs. sum(f(xs)) = 2·sum(xs). A property for every input, not a sample.

2 · Proof

Induction on the list. The empty case is 0 = 2·0; the cons case uses distributivity.

3 · Extract

pipe(map(×2), sum). Correct for all lists, because the proof covers all lists.

The guarantee: correctness for every input. The cost: the proof is at least as hard as the program, and the spec must be complete.

S/V · Lecture 10
02 · Deductive synthesisLecture 10 · Logic as search

Keep the shape, search the holes

Leave holes, then close them.

pipe( ??1 , take( ??2 ) )

A sketch is a partial program with holes. The programmer gives the control flow; the synthesizer fills the constants, guards, or missing expressions. The search collapses to a product of hole domains.

  1. Synthesize a candidate for the current sample.
  2. Verify it against the full specification.
  3. Accept, or add the counterexample to the sample.
  4. Repeat until acceptance or exhaustion.
CEGIS. Sound if the verifier is sound and the hole search is exhaustive. A bounded verifier weakens the guarantee to the bound.
S/V · Lecture 10
03 · Induction & ILPLecture 10 · Logic as search

Examples, and nothing else

Consistent is not correct.

A finite sample is consistent with many hypotheses. The set of them is the version space (Mitchell, 1982). Learning is search through it; the bias decides which consistent hypothesis wins.

S · specific

The most specific hypotheses that cover the positives.

G · general

The most general hypotheses that still exclude the negatives.

Between

Every hypothesis between the boundaries is consistent with the sample. None is proved.

The next input is the one the user will try — and the one the sample did not constrain.

S/V · Lecture 10
03 · Induction & ILPLecture 10 · Logic as search

Inductive logic programming

Learn a clause, not a function.

Given background B, positives E+, and negatives E−, find a hypothesis H such that

B ∪ H ⊨ e for every e ∈ E+
B ∪ H ⊭ e for every e ∈ E−

Cover the positives. Exclude the negatives. The search refines clauses: add literals to specialize, remove them to generalize. The ordering is θ-subsumption.

Language bias is the design. Progol (1995) and Metagol (2016) constrain the clause language so the refinement space stays finite.

ILP's guarantee is consistency with the sample under the clause language — not the intended concept.

S/V · Lecture 10
03 · Induction & ILPLecture 10 · Logic as search

A family, five facts, one clause

Cover the positives. Exclude the negatives.

parent(ali, sara). parent(sara, reza). parent(reza, mina). parent(ali, omar). parent(omar, hana). grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

Positives: (ali,reza), (sara,mina), (ali,hana). Negatives: (ali,sara), (reza,mina).

CandidatePos.Neg.Verdict
gp(X,Y) :- parent(X,Y)0/3yestoo general
gp(X,Z) :- parent(X,Y)3/3yesfree Z
gp(X,Z) :- parent(X,Y), parent(Y,Z)3/3noconsistent

The clause is not proved. It is the simplest hypothesis that fits the language and the sample. A different background could admit another clause; a mislabeled fact could admit none.

S/V · Lecture 10
04 · Proof searchLecture 10 · Logic as search
03 / 08

A proof is a path.

Resolution, unification, and the kernel that checks the certificate.

S/V · Lecture 10
04 · Proof searchLecture 10 · Logic as search

State, rule, closed state

Search for a contradiction.

State

A goal, a sequent, or a set of clauses. The initial state is the premises plus the negated conclusion.

Rule

Resolution: unify a positive and a negative literal, add the resolvent. Unification computes the substitution.

Goal

The empty clause □. It means the clause set has no model, so the original conclusion follows.

The search problem is the choice of pair. n clauses give n(n−1)/2 distinct pairs: 4,950 for 100, 499,500 for 1,000. Each resolvent can create more.

Semi-decision, not decision. A found proof is a proof. A failed search is not a disproof; the next resolution might close the tree.

S/V · Lecture 10
04 · Proof searchLecture 10 · Logic as search

Two refutations

Resolve until the empty clause.

PROPOSITIONAL · P → Q, P ⊢ Q

1. ¬P ∨ Q 2. P 3. ¬Q (negated goal) 4. Q resolve 1, 2 5. □ resolve 4, 3

FIRST-ORDER · ∀x. M(x) → D(x), M(s) ⊢ D(s)

¬M(x) ∨ D(x) M(s) ¬D(s) (negated goal) D(s) resolve with {x ↦ s} □ resolve

The substitution is the interesting step. Unification finds {x ↦ s} without guessing; the tree's leaves are clauses, its root is the empty clause.

S/V · Lecture 10
04 · Proof searchLecture 10 · Logic as search

Where the trust sits

The kernel is the guarantee.

Tactic

A search procedure: goal → subgoals. It can be heuristic, incomplete, or buggy.

Proof term

The artifact the tactic produces. It is data, not a claim.

Kernel

A small checker. If the term type-checks, the proof is valid. No tactic can fake it.

AlphaGeometry. A language model proposes auxiliary constructions; a symbolic deduction engine (DDAR) checks and completes them. The paper reports 25 of 30 olympiad geometry problems within the standard time limit. The model is the proposal; the engine is the check.

The domain formalization is still yours: a proved theorem about the wrong definition is true about the wrong definition.

S/V · Lecture 10
05 · Neural guidanceLecture 10 · Logic as search

A distribution over actions

Three ways a network can help.

Policy

π(a | s) scores the next constructor, clause, premise, or tactic.

Value

v(s) estimates the remaining cost. In best-first, f = g + h.

Proposal

A distribution over programs, lemmas, or constructions that a checker filters.

A learned value is almost never admissible. It can order the frontier well; it cannot certify a solution. The check stays symbolic.

DeepCoder predicts functions · AlphaGeometry proposes constructions · GPT-f proposes proof steps · LLM-Modulo generates candidates for external critics.

S/V · Lecture 10
05 · Neural guidanceLecture 10 · Logic as search

Same model, three consequences

Order, prune, or propose.

UseMechanismCompletenessGuarantee
OrderingBest-first, beam, ranked frontierPreserved if every node is expandedThe checker still decides
PruningDiscard low-scoring branchesLost unless the discard is provableNone beyond the pruning argument
Proposal + checkGenerate; a sound checker filtersInherited from the checkerSound if the checker is sound
The safest architecture is proposal plus check. The fastest is often pruning. The most defensible is ordering plus a final check.

A score is not a certificate. A candidate that passes the checker is.

S/V · Lecture 10
05 · Neural guidanceLecture 10 · Logic as search

Interactive · the same search, two disciplines

Same answer. 51× the search.

SPECIFICATION · the lab's default preset

[1,2,3,4] → [3,5,7,9] [0,1,2] → [1,3,5] [2,3] → [5,7]

DSL: map, filter, count, reverse, sort, take, drop, sum, pipe. Cost bound 5.

ModeExpandedPrunedAnswer
typed———
untyped———

Press a button to run the enumerator over this grammar.

The type checker is a sound prune. Removing ill-typed terms cannot lose a consistent program; it only removes work. The answer is identical.
S/V · Lecture 10
06 · Guarantees & costsLecture 10 · Logic as search

Relative to what?

Every guarantee has a relative clause.

MethodSoundnessCompletenessFailure
EnumerationAgrees with every exampleUp to the cost boundNo program in the bound
ILPCovers positives, excludes negativesFor the sample, not the conceptOvergeneralization; noise
Sketch / CEGISIf the verifier is soundFor the finite hole domainBounded verifier; bad sketch
ResolutionA derived □ is a refutationRefutation-complete; may not terminateTimeout means unknown
Neural-guidedInherited from the checkerOnly if guidance is orderingFalse pruning; shift

Language · specification · resource bound. Omit one and the claim becomes a hope.

S/V · Lecture 10
06 · Guarantees & costsLecture 10 · Logic as search

The bill has four lines

Search is only one of them.

Search

Nodes × cost per node. Types and dedup cut the first; fast evaluation cuts the second. A heuristic cuts the average, not the worst case.

Verification

Examples are cheap; proofs are expensive; a proof term is cheap once it exists. The gap is the specification gap.

Specification

Examples are weak; a full spec is strong but costly; a sketch encodes insight. Usually the largest term, and it is human.

A tighter DSL buys search and costs coverage. The lab's 16× gap between typed and raw at cost 4 is a small, measured version of the trade.

The question is not “which DSL is more expressive?” but “which makes the intended program simple and the lookup table impossible?”

S/V · Lecture 10
07 · CasesLecture 10 · Logic as search

One pattern, five systems

Spec, space, search, checker.

SystemSearch spaceLearned partChecker
FlashFillString DSL; version-space algebraNone; cost heuristicExact examples
DeepCoderList DSL; DFS enumerationPredicts likely functionsInterpreter
DreamCoderGrowing library; wake–sleepAbstraction inventionProgram execution
AlphaGeometryAuxiliary constructions; DDARProposes constructionsDeduction engine
GPT-fMetamath proof stepsProposes steps/premisesMetamath kernel

The numbers are the papers' claims. The architecture is the transferable part: which component is learned, and which one is trusted.

S/V · Lecture 10
07 · CasesLecture 10 · Logic as search

A case in one loop

Propose, deduce, check.

  1. The language model proposes an auxiliary construction: a point, a line, a circle.
  2. The deduction engine DDAR applies the rules and algebraic reasoning.
  3. If the goal closes, the construction and proof are kept. Otherwise the model tries another.
25 of 30 olympiad geometry problems within the standard time limit, as reported by the authors. Not an independent replication.

The model's output is not the theorem. The theorem is the proof term the engine derives. The model is judged by how often it proposes something the checker can use.

This is the pattern in one system: a neural proposal distribution over a discrete action space, a symbolic search that completes the proof, and a checker that makes the result a certificate.

S/V · Lecture 10
08 · RecapLecture 10 · Logic as search

What you should be able to do

Four moves.

Space

Name the DSL, cost, examples, and bound. Count the space before you search it.

Direction

Deduction is correct by construction; induction is consistent with a sample.

Proof

Resolution is refutation; a found □ is a proof; a timeout is unknown.

Guidance

Order, prune, or propose. Only proposal-plus-check inherits soundness.

S/V · Lecture 10
08 · RecapLecture 10 · Logic as search

What this does not buy

Three honest limits.

Examples are not a spec

A finite sample is consistent with many programs. The DSL and cost decide which one you get; they do not recover the intended function.

A check is not a proof

Testing on examples, type-checking, and kernel-checking are different guarantees. Ask which one a paper means.

Guidance is not a guarantee

A learned score can order, prune, or propose. Only the checker can say the answer is right.

And every benchmark is narrower than the domain it evokes. The architecture transfers more reliably than the number.

S/V · Lecture 10
08 · RecapLecture 10 · Logic as search

Next · hands-on

Now watch the space.

Open the lab. Give the synthesizer examples. Step through the candidates, turn type pruning off, and compare the counters. The answer will be the same; the search will not.

Lab 10 · program synthesis → open the lab

S/V · Lecture 10
Speaker notes