Lecture 12 · Deduction at scale

Deduction at scale.

The model writes the formula. The solver checks the consequence. The solver is right about the formula — and the formula may be wrong about the text.

9 sections 4 systems 1 solver lab Self-paced
00 · Learning objectivesLecture 12 · Deduction at scale

By the end of this lecture

Four things you can do.

01

Trace the loop

Propose, formalize, solve, check, repair — and separate the internal check from the external one.

02

Read a formalization

Spot direction, scope, and counting errors in “only if”, “unless”, and quantifier order.

03

Locate the guarantee

Say what the solver proves, and what it proves it about.

04

Name the failure

Formalization error, solver error, or benchmark leakage — and what each one looks like.

S/V · Lecture 12
00 · The hookLecture 12 · Deduction at scale

One key, three signs

Exactly one sign is true.

Exactly one box contains the key. Each box carries one inscription.

  1. Box A says: the key is in B.
  2. Box B says: the key is in A or in C.
  3. Box C says: the key is not in A.

Exactly one inscription is true. Which box holds the key?

Write it down

atoms A, B, C
EO(A, B, C)
signs: B, A ∨ C, ¬A
EO(signs)
EO = exactly-one

The formula is a conjunction of a location constraint and a counting constraint. The solver sees only the formula. It never sees the English.

S/V · Lecture 12
00 · The hookLecture 12 · Deduction at scale

One literal apart

Three valid proofs.

Formalization · EO = exactly-oneChangeModelAnswer
F1 · EO(B, A∨C, ¬A)the textAA
F2 · EO(¬B, A∨C, ¬A)sign A negatedBB
F3 · EO(B, A∨C, ¬C)sign C’s atomCC

Each formula is satisfiable, each has exactly one model, and the solver is equally sound in all three cases.

A wrong formalization does not produce an error message. It produces a proof.

S/V · Lecture 12
01 · The loopLecture 12 · Deduction at scale
01 / 08

Five stages, two checks.

The solver checks the artifact. Something else has to check the formula.

S/V · Lecture 12
01 · The loopLecture 12 · Deduction at scale

The architecture

From text to consequence.

01
Propose
The model reads the text and drafts a formalization.
neural
02
Formalize
Fix the vocabulary, the syntax, and the background axioms.
unverified
03
Solve
The oracle returns a model, unsat, a proof, or a plan.
sound relative to F
04
Check
Evaluate the artifact; compare the formula to the text.
two checks
05
Repair
Feed the diagnostic back; revise or accept.
iterate
text "Every cube is red. a is a cube. Is a red?" F ∀x (Cube(x) → Red(x)) ∧ Cube(a) artifact proof of Red(a) — checkable; the translation is not.

The solver’s guarantee begins at stage 03. Stages 01–02 are the part it cannot see.

S/V · Lecture 12
01 · The loopLecture 12 · Deduction at scale

Do not conflate them

Two checks, two failures.

Internal check

Does the artifact satisfy the formula? Evaluate the model, simulate the plan, type-check the proof term.

mechanical · cheap · relative to F

External check

Does the formula say what the text says? Read both, and argue that they agree on every case the question can distinguish.

not mechanical · the fidelity gap

Only the external check can catch a wrong formalization. A parser, a solver, and a proof checker all pass a formula that means the wrong thing.

S/V · Lecture 12
01 · The loopLecture 12 · Deduction at scale

The division of labour

Who guarantees what.

Textwhat the reader means
Modelproposes a formula; no guarantee
Formula Fsyntax + vocabulary + axioms
Solversound relative to F; complete for its fragment
Artifactmodel / unsat / proof / plan
The red link is unverified. The teal link is the guarantee. They are not the same link.
LinkOwnerWhat can be checked
Text → formulaModelFidelity, by a human or a second translation
Formula → artifactSolverSoundness relative to F; completeness for the fragment
Artifact → decisionSystem designerWhether the artifact answers the question asked

The model is a translator, not an authority. The solver is an authority about the formula, not about the text.

S/V · Lecture 12
02 · FormalizersLecture 12 · Deduction at scale
02 / 08

Translation is a decision.

“Only if”, “unless”, and quantifier scope are choices the text leaves open and the formula must close.

S/V · Lecture 12
02 · FormalizersLecture 12 · Deduction at scale

What every formalization decides

Six quiet choices.

DecisionExampleFailure
Vocabulary“open” → Open(d) or ¬Closed(d)a predicate the domain does not use
Direction“if P then Q” vs “Q only if P”the converse
Scope“everyone loves someone”∀∃ swapped with ∃∀
Countingexactly / at least / at most oneunder- or over-constrained
Backgrounddefaults, closed world, arithmeticunexpected models
Sortsobjects, events, times, quantitiestype error or nonsense

Grammar-constrained decoding fixes the syntax row. It does not touch the other five.

S/V · Lecture 12
02 · FormalizersLecture 12 · Deduction at scale

Direction

“Only if” is not “if.”

The alarm sounds only if the door is open. The door is a necessary condition, so the implication runs from alarm to door:

A → O

  • A, A → O entails O. Modus ponens.
  • ¬O, A → O entails ¬A. Modus tollens.
  • O, A → O does not entail A. The door can be open with the alarm silent.
S/V · Lecture 12
02 · FormalizersLecture 12 · Deduction at scale

Scope

Two readings, one sentence.

Reading 1

∀x ∃y L(x, y)

Everyone has someone: each person may love a different person.

Reading 2

∃y ∀x L(x, y)

There is someone for everyone: one person is loved by all.

Reading 2 entails reading 1. Reading 1 does not entail reading 2: in a two-person domain where each loves the other, everyone loves someone, but no single person is loved by everyone.

S/V · Lecture 12
03 · SolversLecture 12 · Deduction at scale
03 / 08

An oracle for the language.

A solver decides consequences of a formula. It knows nothing about the sentence the formula came from.

S/V · Lecture 12
03 · SolversLecture 12 · Deduction at scale

Different oracles, different costs

The solver ladder.

FamilyInputOutputWorst caseGuarantee
SATCNFmodel / refutationNP-completesound, complete
SMTtheoriesmodel / unsat / unknowntheory-dependentsound; complete for fragments
ProverFOLproofundecidablerefutation-complete in principle
PlannerPDDLplanPSPACE-completerelative to the domain
Kernelproof termaccept / rejectdecidablerelative to axioms

The complexity is a property of the language. The fidelity of the input is a property of the pipeline. The oracle answers only what its language can express.

S/V · Lecture 12
03 · SolversLecture 12 · Deduction at scale

The standard reduction

To prove q, refute ¬q.

F ⊨ q  ⟺  F ∧ ¬q is unsat

UNSAT is the yes

An unsat answer to the refutation query means the query follows. The solver’s negative is the logician’s positive.

But if F is unsat…

…then F ∧ ¬q is unsat for every q. The solver proves everything. Inconsistency is not a strong result; it is a broken premise set.

S/V · Lecture 12
03 · SolversLecture 12 · Deduction at scale

Evidence, not just answers

What comes back matters.

Model

Self-certifying: evaluate the formula under the assignment. A wrong model is easy to catch.

UNSAT

Not self-certifying: you need a proof log, an unsat core, or trust in the solver.

Unknown

Certifies nothing. A timeout is not evidence that no model or plan exists.

Check the artifact, not the tool. If the tool emits no checkable artifact, record that the answer rests on trust.

S/V · Lecture 12
03 · SolversLecture 12 · Deduction at scale

Interactive · the wet pavement

Choose a reading. Run the check.

If it rained, the pavement is wet.

If the sprinkler ran, the pavement is wet.

The pavement is wet.

Did it rain?

Solver answer — 8 assignments

—

Choose a reading.

Reading 1 selected.
S/V · Lecture 12
04 · Tool use & repairLecture 12 · Deduction at scale

Closing the loop

A search over formalizations.

The loop does not search for the answer. It searches for a formula that passes a check. The check decides what the search can find.

1
Draft
The model writes a formula from the text and the current diagnostic.
2
Solve
The oracle returns a model, unsat, a core, or a plan.
3
Diagnose
Extract the most informative artifact: countermodel, core, trace.
4
Revise
Append the diagnostic and ask again; accept or stop at budget.

Signal quality, best to worst: countermodel → unsat core → unsat → type error → parse error.

S/V · Lecture 12
04 · Tool use & repairLecture 12 · Deduction at scale

Same anatomy, different oracles

Five systems.

SystemModel writesOracleGuarantee
Logic-LMa symbolic formulationSAT / SMT solverrelative to the formulation
LLM+PPDDL domain + problemclassical plannerrelative to the PDDL model
PALa Python programinterpreteroutput of that program
ReActthoughts + tool callsany toolnone formal
LLM-Modulocandidate plans / proofsexternal criticsconditional on the critics

The names differ; the tuple is the same: model output, oracle, feedback, guarantee.

S/V · Lecture 12
05 · Failure modesLecture 12 · Deduction at scale

Failure family 01

The formula can be wrong.

Predicate

“Open” → Closed(d)

A unique wrong model. No internal signal; only a human or a test can catch it.

Direction

A → O becomes O → A

A different implication. The solver proves a different claim with the same confidence.

Scope

∀∃ becomes ∃∀

A stronger claim. A countermodel can expose it, but only if you ask for one.

A formalization error can be satisfiable, have exactly one model, and entail the wrong answer. The solver compares symbols with symbols, never symbols with text.

S/V · Lecture 12
05 · Failure modesLecture 12 · Deduction at scale

Failure family 02

The solver can be right and useless.

  • Mis-encoding. A correct solver on a CNF that does not encode the intended formula. Tseitin auxiliaries are a common source.
  • Timeout. An undecidable fragment or a hard instance. Unknown is not “no,” and it is not a negative label.
  • Unsound axiom or validator. A sound kernel plus a user axiom that trivializes the statement; a validator that shares a bug with the generator.

Solver bugs are rare. The failures around the solver are common. Check the artifact, not the tool.

S/V · Lecture 12
05 · Failure modesLecture 12 · Deduction at scale

Failure family 03

The benchmark can leak.

  • Pretraining. The item and its answer are in the corpus.
  • Prompt. Few-shot exemplars are test items.
  • Ontology. The domain or schema is given; only slots are filled.
  • Loop. The repair step sees the gold answer.

Why it matters

Leakage makes recall look like reasoning. A high score can coexist with a bad formalization, because the model never needed the solver.

Defenses: held-out templates · renamed constants · unseen domains · formalization-only tests

Leakage flatters every other failure. A high score can be recall, not deduction; evaluate the formalization separately.
S/V · Lecture 12
06 · What is guaranteedLecture 12 · Deduction at scale

A conditional, not a slogan

Four antecedents.

(i) Solver sound

If it answers, the answer is true for the logic.

mechanical · proof log or kernel

(ii) Encoding equisat

The solver input has a model exactly when the intended formula does.

proof obligation · Tseitin

(iii) F faithful to T

The formula means what the text means.

unverified · the hard one

(iv) q formalizes Q

The query is the question that was asked.

unverified · ambiguity

The solver touches (i) and (ii). The model contributes to (iii) and (iv) and certifies neither.

S/V · Lecture 12
06 · What is guaranteedLecture 12 · Deduction at scale

Easy to lose

Three distinctions.

Model ≠ proof

A model shows consistency. Entailment is truth in every model. A witness is not a universal.

UNSAT ≠ “no”

Refuting ¬q proves q. If F itself is unsat, everything follows. The same status, two meanings.

Proof ≠ statement

A kernel checks the proof term against the theorem. It does not check that the theorem is the English claim.

These are the three places where a correct-sounding sentence (“the solver proved it”) hides a different claim.

S/V · Lecture 12
06 · What is guaranteedLecture 12 · Deduction at scale

The sentence to remember

The solver guarantees a theorem about the formalization. The model only proposes it.

sound relative to F · never sound relative to English

Guaranteed

If the formalization is right, the solver's answer follows; the proof is checkable.

Not guaranteed

That the formalization means what the English means, or that the premises are true.

S/V · Lecture 12
07 · CasesLecture 12 · Deduction at scale

Read them along the tuple

Math and planning.

AlphaGeometry

Propose, then deduce

The model proposes auxiliary constructions; a deduction engine closes and checks the proof. The paper reports 25 of 30 IMO-level geometry problems within the olympiad time limit.

Unverified: the formal statement.

LLM+P

Translate, then plan

The model writes PDDL; a classical planner returns a plan correct or optimal for that model. The model alone fails to produce feasible plans on most of the benchmark.

Unverified: the PDDL domain.

Both put the oracle in the symbolic component. Both leave the translation outside the guarantee.

S/V · Lecture 12
07 · CasesLecture 12 · Deduction at scale

Read them along the tuple

Code and logic.

PAL

Write, then execute

The model writes a program; an interpreter runs it. The paper reports a 15-point absolute gain for PAL with Codex over PaLM-540B with chain-of-thought on GSM8K. The output is the program’s output.

Unverified: the specification.

Logic-LM

Translate, solve, refine

The model writes a symbolic formulation; a solver reasons; solver errors drive refinement. The paper reports +39.2% over standard prompting across five datasets.

Unverified: the formulation.

PAL’s oracle checks execution; Logic-LM’s oracle checks consequence. Neither checks meaning.

S/V · Lecture 12
08 · RecapLecture 12 · Deduction at scale

The four moves

What to carry forward.

01 · Loop

Propose, formalize, solve, check, repair. Two checks, not one.

02 · Formalize

Direction, scope, counting: the decisions the text leaves open.

03 · Guarantee

Soundness is relative to F. Fidelity is the unverified part.

04 · Fail

Formalization, solver, leakage. Check the artifact, not the tool.

Relative to the formalization.

S/V · Lecture 12
08 · RecapLecture 12 · Deduction at scale

Next · hands-on

Prove the wrong box.

Open the lab. Run the three candidates on the three-box puzzle. Each proof is valid; only one formula matches the text.

Lab 12 · formalize and check → open the lab

S/V · Lecture 12
Speaker notes