Course / Act IV · The inferences Lecture 12

Deduction at scale.

A language model reads a puzzle and writes a formula. A solver enumerates the models and returns an answer. The solver is right. The formula may not be. This lecture is about the gap between those two sentences.

~50 min read 3 worked formalizations 1 solver lab 10 quiz questions Updated 2026-11-17

Three boxes sit on a table. Exactly one contains a key. Box A says the key is in B; box B says the key is in A or in C; box C says the key is not in A. Exactly one inscription is true. Which box holds the key?

00 / The hookA valid proof of the wrong answer.

A fluent model can produce a confident paragraph. A constructed illustration, not a transcript: “If the key were in A, two signs would be true, so not A. If the key were in C, B and C would both be true. So the key is in B.” The first step is false — with the key in A, only B’s sign is true — but the conclusion still sounds supported. That is the trouble with a chain of thought as a certificate: without a semantics, a reader cannot separate a valid step from a plausible one.

Write the puzzle down. Let A, B, and C mean that the key is in the corresponding box. “Exactly one box” is a counting constraint; each inscription is a formula; the puzzle is their conjunction:

F1 = exactly-one(A, B, C) ∧ exactly-one(B, A ∨ C, ¬A)
(0.1)

Three candidate worlds, one per box. The answer is the world in which the formula is true — deduction by enumeration.

Table 0.1 · The three-box puzzle, enumerated. A world is a row; the formula is true in exactly one of them.
Key inA says “B”B says “A ∨ C”C says “¬A”True signsModel?
Afalsetruefalse1yes
Btruefalsetrue2no
Cfalsetruetrue2no

The answer is A. A solver returns it with a witness, because it does not reason in prose; it searches assignments. Write M(F) for the assignments that satisfy F. The two notions the rest of the lecture depends on are:

M(F) = { σ ∈ {0,1}n : σ ⊨ F }    and    F ⊨ q  ⟺  M(F) ⊆ M(q)
(0.2)

A formula is satisfiable when it has at least one model. It entails a query when every model of the formula is a model of the query. The solver decides both questions for this language, and its answer is a theorem about F1 — not about the boxes. Nothing in the solver connects A, B, and C to the table. That connection is the formalization, and the formalization was written by a model that makes mistakes.

Change one symbol: read box A’s sign as “not in B” and the model becomes B; read box C’s as “not in C” and it becomes C:

F2 = exactly-one(A,B,C) ∧ exactly-one(¬B, A∨C, ¬A)     F3 = exactly-one(A,B,C) ∧ exactly-one(B, A∨C, ¬C)
(0.3)

Three formulas, one literal apart, each satisfiable with one model. The solver is equally sound in all three and returns three different answers with equal confidence. A wrong formalization does not produce an error message; it produces a proof.

Caveat · the puzzle is built to be small

The puzzle fits on one screen and one literal flips the answer. Real text is worse: anaphora, ellipsis, implicature, defaults, and domain vocabulary sit between sentence and formula. The puzzle does not show that formalization always fails. It shows that a solver cannot detect the failure from the inside.

Remember: the solver guarantees a theorem about the formalization; the language model only proposes the formalization.

01 / The loopPropose, formalize, solve, check, repair.

A deduction-at-scale system is a loop with five stages and two kinds of check.

Definition · the five-stage loop

Given a text T and a formal system L with a solver S: a proposer P maps T to a formalization F ∈ L; S maps F to an artifact (a model, an unsat answer, a proof, a plan); a check C compares the artifact to T; and a repair step R uses the diagnostic to revise F. It repeats until the check accepts, the budget runs out, or the proposer stops changing.

One iteration maps the current formula to a diagnostic and the diagnostic to the next formula:

dt = D(S(Ft), Ft)     Ft+1 = P(T, Ft, dt)
(1.1)

The loop runs until a condition is met, and the condition is the interesting part. Figure 1.1 separates the two checks, because conflating them is the most common mistake in the literature.

The propose–formalize–solve–check–repair loop A text is translated by a proposer into a formula. A solver returns a model, an unsat answer, a proof, or a plan. A check compares the artifact to the formula and, separately, the formula to the text. A repair arrow returns a diagnostic to the proposer. The solver’s guarantee is relative to the formula; the text-to-formula step is not mechanically checkable. THE LOOP TEXT natural language facts + question PROPOSE LLM formalizer candidate formulas FORMULA F syntax + vocabulary + background axioms SOLVE SAT / SMT / prover planner / checker CHECK artifact vs F F vs text REPAIR · parse error · unsat core · countermodel · plan trace SOLVER’S GUARANTEE · RELATIVE TO F NOT MECHANICALLY CHECKABLE the fidelity gap: F may not mean what T says
Fig. 1.1 A schematic, not a system diagram. The teal boundary encloses what the solver can certify; the red boundary encloses what it cannot — the step from text to formula.

Two checks, not one

The internal check asks whether the artifact satisfies the formula. It is mechanical: evaluate the model, simulate the plan, type-check the proof term. It is cheap and does not require trusting the solver’s internals. The external check asks whether the formula says what the text says. It is not mechanical: it requires reading both and arguing that they agree on every case the question can distinguish.

Table 1.1 · The two checks. They fail in different ways and need different evidence.
CheckQuestionWho can answer itFailure looks like
InternalDoes the artifact satisfy F?A parser, an evaluator, a proof checker, a plan validatorA solver or checker bug; a malformed encoding
ExternalDoes F mean what T means?Human review, tests, a second independent formalizationA valid proof of the wrong answer

The loop terminates in four ways, and only one is success: accept, when both checks pass; budget exhaustion; oscillation, when a repair fixes one symptom and reintroduces another; or refusal, when the proposer cannot produce a formula that parses. A system that reports only the final answer hides which one happened.

The repair step is only as good as its signal. A parse error localizes the fault to syntax; unsat says the constraints cannot all hold; an unsat core narrows the set to an inconsistent subset; a countermodel is a concrete assignment in which the formula is true and the expected conclusion is false. The countermodel is the most informative: the proposer can see which premise is missing. §4 returns to this hierarchy.

Caveat · the loop is not a proof

A loop that accepts has established only that the artifact passes the check. If that check is a solver, it is consequence relative to the formula. Only an external check can say anything about the text, and it is an argument, not an algorithm.

02 / LLMs as formalizersTranslation is a decision, not a transcription.

The proposer’s job sounds like translation, but a formalization makes decisions the text leaves implicit, and each can be wrong in a way that leaves the formula well-formed.

Table 2.1 · Six decisions every formalization makes, whether or not the author notices.
DecisionExampleWhat goes wrong
Vocabulary“the door is 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; a valid argument for the wrong claim
Scope“everyone loves someone”∀∃ swapped with ∃∀
Counting“exactly one”, “at least one”, “at most one”An under- or over-constrained formula
Background“birds fly”; “the meeting is on Tuesday”Defaults and closed-world assumptions left out
Sortsobjects, events, times, quantitiesEntities conflated with predicates

Language models are genuinely useful here: they can produce a PDDL domain, a Prolog clause, a SQL query, or a Lean tactic block that parses. Logic-LM reports an average 39.2% improvement over standard prompting and 18.4% over chain-of-thought across five logical-reasoning datasets (arXiv:2305.12295). LLM+P reports optimal plans on most of its benchmark problems when the model writes PDDL and a planner solves it, while the model alone fails to produce feasible plans on most (arXiv:2304.11477). These gains share a structure: the model writes a formal object, and something else reasons.

The same models are unreliable at the decisions in Table 2.1. The training signal rewards a plausible continuation, not a faithful translation. Dziri et al. show that transformer performance on compositional tasks degrades with the depth of the required computation and relies on patterns seen in training (arXiv:2305.18654). A formalization is compositional, and that is the regime where a fluent large language model is least reliable.

Worked example: “only if”

“The alarm sounds only if the door is open.” “Only if” is not “if.” The door’s being open is a necessary condition for the alarm, so the implication runs from the alarm to the door:

A → O     (the alarm sounds only if the door is open)
(2.1)

One row is false: A true and O false. Three patterns are worth checking; one fails:

  • Modus ponens. A and A → O entail O.
  • Modus tollens. ¬O and A → O entail ¬A.
  • Affirming the consequent. O and A → O do not entail A. The door can be open with the alarm silent.

The third is a formal fallacy but a natural conversational inference: if the only stated route to O is A, a listener may assume the route is exhaustive. Formalization must decide; if the text does not say, the formula should not either. “Unless” reverses the polarity: “Unless the door is open, the alarm sounds” is ¬O → A, not A → ¬O. The readings disagree when the door is open and the alarm sounds.

Worked example: quantifier scope

“Everyone loves someone.” Two readings are available, and they are not equivalent:

∀x ∃y L(x, y)     versus     ∃y ∀x L(x, y)
(2.2)

The second entails the first: if one person is loved by everyone, everyone loves someone. The first does not entail the second: in a two-person domain where each loves the other, everyone loves someone, but no single person is loved by everyone. A formalizer that swaps them has made a semantic error, not a syntax error, and the solver will not notice.

Syntax is cheap; fidelity is not

A grammar-constrained decoder eliminates the parse-error class: every completion is well-formed. It does not touch the semantic classes. A grammar can tell you that A → O is a formula; it cannot tell you that the text said O → A.

Caveat · benchmark accuracy is not fidelity

A formalization benchmark usually scores the final answer. A model can score well by guessing, by exploiting a template, or by writing a formula weak enough to entail the gold label for the wrong reason. To measure fidelity you need “undetermined” answers, one-literal flips, and held-out vocabulary.

03 / Solvers as oraclesWhat the solver decides, and what it does not.

An inference engine is an oracle when it answers a decision question about a formal object and its answer depends only on the formal semantics. In a pipeline it is usually a SAT solver, an SMT solver, a theorem prover, a planner, or a constraint solver.

Table 3.1 · The solver ladder. “Sound” means the answer is true whenever it is returned; “complete” means an answer is returned whenever one exists.
FamilyInputOutputWorst caseGuarantee
SATCNF over Boolean variablesA model, or a refutationNP-complete (Cook, 1971)Sound and complete
SMTFormulas over theoriesA model, unsat, or unknownTheory-dependent; some fragments undecidableSound; complete for decidable fragments
First-order proverFOL axioms and a conjectureA proof, or a saturated setUndecidable (Church–Turing)Sound; refutation-complete in principle
PlannerPDDL domain and problemA plan, or no planPSPACE-complete (Bylander, 1994)Sound relative to the domain; optimality depends
Proof assistantA statement and tacticsA proof termThe kernel is decidableSound relative to the kernel and axioms
Datalog / ASPFacts and rulesA fixpoint or stable modelPTIME / NP-hardSound and complete for the fragment

The table hides the most important fact: a solver is a decision procedure for a language, not a text. A SAT solver knows nothing about boxes or keys; it knows propositional clauses and assignments. “Satisfiable” means it found an assignment making a set of clauses true. Whether that assignment is a possible arrangement of keys is a question for whoever wrote the clauses.

Entailment by refutation

The standard way to ask “does F entail q?” is to ask whether the negation of the query is consistent with the premises:

F ⊨ q  ⟺  F ∧ ¬q is unsatisfiable
(3.1)

This reduction makes SAT solvers into entailment engines and explains two surprises. First, an unsat answer to the refutation query is the positive answer: the query follows. Second, if F is itself unsatisfiable, F ∧ ¬q is unsatisfiable for every q, so the solver “proves” anything. Inconsistency proves everything, not nothing.

Worked example: the three boxes in CNF

To see where encoding errors enter, put the puzzle into CNF. The atoms are A, B, C for the location and s1, s2, s3 for the inscriptions. “Exactly one box” is a cardinality constraint; each inscription is a definition.

; exactly one box (A ∨ B ∨ C) (¬A ∨ ¬B) (¬A ∨ ¬C) (¬B ∨ ¬C) ; s1 ↔ B, the sign on box A (¬s1 ∨ B) (s1 ∨ ¬B) ; s2 ↔ (A ∨ C), the sign on box B (¬s2 ∨ A ∨ C) (s2 ∨ ¬A) (s2 ∨ ¬C) ; s3 ↔ ¬A, the sign on box C (¬s3 ∨ ¬A) (s3 ∨ A) ; exactly one sign is true (s1 ∨ s2 ∨ s3) (¬s1 ∨ ¬s2) (¬s1 ∨ ¬s3) (¬s2 ∨ ¬s3)

A solver returns, among others, A = 1, B = 0, C = 0, s1 = 0, s2 = 1, s3 = 0. Check it: the first clause holds by A; the at-most-one clauses by B and C being false; s1 because both sides are false; s2 and A ∨ C because both are true; s3 and ¬A because both are false; exactly one si is true.

The encoding is not cosmetic. The clauses for s2 ↔ (A ∨ C) preserve satisfiability but introduce auxiliaries; forget to project them, or use the wrong polarity, and the solver still solves a well-formed SAT problem — just not the intended one.

What a solver can return

Outputs carry different evidence. A model is self-certifying: evaluating F under the assignment is cheap. An unsat answer is not: it claims no assignment exists, and checking it requires a proof, an unsat core, or trust. A plan is checked by simulation and a proof term by a kernel.

Table 3.2 · Solver outputs and the evidence they carry.
OutputWhat it certifiesHow to check itWhat you still trust
SAT + modelThe formula is consistent; the model satisfies itEvaluate the formula under the assignmentThe parser and the evaluator
UNSATNo model existsA proof log (for example DRAT) or an unsat core; otherwise nothingThe solver, if no proof is emitted
UNSAT coreA subset of the constraints is already inconsistentRe-solve the subset, or check its proofThe solver and the core extractor
PlanThe goal is reachable under the domainSimulate the plan step by stepThe domain model and the validator
Proof termThe statement follows from the axiomsType-check with a small kernelThe kernel and the axioms
Unknown / timeoutNothing——
Caveat · a timeout is not a “no”

SMT solvers return unknown outside a decidable fragment, and planners and provers can run out of time. An unknown answer is not evidence that no model or plan exists.

Complexity citations: Cook, “The Complexity of Theorem-Proving Procedures,” STOC 1971; Bylander, “The Computational Complexity of Propositional STRIPS Planning,” Artificial Intelligence, 1994.

04 / Tool use & repairThe model proposes; the tool disposes.

The names matter less than the tuple: what the model produces, what the oracle decides, what feedback returns, and what the guarantee covers.

Table 4.1 · Five systems, read along the same tuple.
SystemModel producesOracleFeedbackGuarantee
Logic-LMA symbolic formulationSAT/SMT or a logic solverSolver error messages; refinementRelative to the formulation
LLM+PA PDDL domain and problemA classical plannerPlan or failureRelative to the PDDL model
PALA Python programA Python interpreterOutput or exceptionThe program runs; not that it is right
ReActThoughts and tool callsAny toolObservationsNone formal
LLM-ModuloCandidate plans or proofsExternal critics and verifiersCritiques; iterateConditional on the critics

Logic-LM is the loop in §1: the model writes a formulation, a solver reasons, and solver error messages are appended to the prompt for revision. The gains are substantial; the open question is whether a successful solve means the formulation captured the problem.

LLM+P moves the guarantee toward the symbolic side: the model writes PDDL, a classical planner returns a plan correct or optimal for that description, and the unverified link is the grounding of text in the domain’s predicates. A wrong domain can make a valid plan useless.

PAL is a different trade: the model writes a program and an interpreter runs it. The guarantee is that the output is the program’s output, not that the program computes the intended function. An off-by-one program runs perfectly. The harder the specification, the less the interpreter can do.

ReAct interleaves thoughts, tool calls, and observations. It is a control loop, not a verification architecture: nothing checks that the final answer follows from the observations.

LLM-Modulo makes the division explicit: the model proposes, external model-based verifiers critique, and the loop runs until the critics accept or the budget ends. The guarantee is conditional on the critics’ coverage; a critic that checks the plan but not the domain cannot catch a wrong domain.

The repair signal hierarchy

From most to least informative: a countermodel gives an assignment that satisfies the formula and falsifies the expected conclusion; an unsat core gives a small inconsistent subset; unsat says only that the whole set is inconsistent; a type error says a term is in the wrong place; a parse error says the string is not in the language. Ask for the most informative artifact the solver can produce — a model, not a Boolean; a core, not just unsat; a plan trace, not just a plan. It is usually cheaper than another model call and gives the proposer something specific to fix.

Caveat · formalization gaming

If the loop is scored by whether the solver returns the expected answer, the proposer can add the expected answer as an axiom: the formula becomes satisfiable, the query is entailed, and the score improves. This is the symbolic analogue of reward hacking. The acceptance check must be independent of the answer it judges — a human reading the formula, a held-out test, or a second formalization.

05 / Failure modesThree families, and one that hides inside the others.

When a deduction pipeline produces a wrong answer, the cause is usually one of three families: the formalization is wrong, the solver is wrong, or the evaluation is contaminated. The third is the least visible, because it makes the first two look better than they are.

Formalization errors

A formalization error is any mismatch between formula and text. The taxonomy below is not exhaustive, but it covers the recurring cases. The symptom column matters because it tells you which check can catch the error — and, often, that no automatic check can.

Table 5.1 · Formalization errors and their symptoms.
ErrorExampleSymptomCaught by
Wrong predicate“open” → Closed(d)A unique wrong modelOnly a human or a test
Wrong directionA → O written as O → AA different implication; a wrong entailmentA countermodel query
Wrong scope∀∃ written as ∃∀A stronger or weaker formulaA countermodel, if you ask for one
Wrong counting“exactly one” → “at least one”Many models; an undetermined answerA model count
Missing backgroundA default or closed-world assumption omittedUnexpected modelsA human reading the models
Over-constraintContradictory axiomsUnsat; explosionThe solver, but it reports “unsat,” not “wrong”
Sort errorAn event used as an objectA type error or a nonsense modelThe parser, if the language is typed

The first row is the killer. A wrong predicate can produce a formula that is satisfiable, has exactly one model, and entails the wrong answer. The solver cannot compare Open(d) with the English word “open”; it can only compare symbols with symbols. The three variants in §0 differ by one symbol, each has one model, and the answers are A, B, and C. No internal signal distinguishes the faithful one.

Solver errors

Solver bugs are real but rare, and they are not the main risk. The main risks are one level up: a mis-encoding, a timeout, an unsound axiom, or a validator that shares a bug with the generator. A SAT solver correct on CNF can be given a CNF that does not encode the intended formula; a planner correct on PDDL can be given a domain with wrong preconditions. The discipline is to check the artifact, not the tool: evaluate the model, simulate the plan, keep the proof log when the solver says unsat. If the tool emits no checkable artifact, record that the answer rests on trust. That is the difference between a guarantee and a promise.

Benchmark leakage

Leakage makes the other two look better than they are. There are at least four routes:

  • Pretraining contamination. The test item and its answer are in the model’s training corpus; the model may recall the answer without formalizing anything.
  • Prompt leakage. Few-shot exemplars are test items or near-duplicates; the model has seen the template and the constants.
  • Ontology leakage. The predicate vocabulary, PDDL domain, or schema is given, so the model only fills slots. That is a legitimate setting, but not the same task as formalizing from scratch.
  • Answer leakage through the loop. The repair loop is given the gold answer, or the checker encodes it; the loop “converges” by construction.

PlanBench makes the general point sharply: on common-sense planning tasks it is hard to tell whether a model is planning or retrieving from its world knowledge (arXiv:2206.10498). The defenses are unglamorous: hold out templates, not just instances; rename constants and predicates; evaluate the formalization separately; ask for the answer with and without the solver; use an unseen domain; audit the prompt for test items. None proves the absence of leakage, but together they make it harder to mistake recall for deduction.

Caveat · “the solver said so” is not an evaluation

A pipeline can be sound at every step and wrong end to end, because the formalization is wrong. Accuracy measures the end-to-end answer, not the soundness of the steps. If the benchmark is contaminated, accuracy can be high while the formalization is bad. The failures compound: leakage hides formalization errors, and formalization errors make leakage look like reasoning.

06 / What is guaranteedA guarantee, four antecedents.

The honest statement of the guarantee is a conditional. It is not “the system is correct.” It is “if four things hold, then the answer is correct for the text.” Each antecedent is an obligation, and only the first is mechanical.

The guarantee schema (not a theorem)

If (i) the solver is sound for the logic, (ii) the encoded input F′ is equisatisfiable with the intended formula F, (iii) F is a faithful formalization of the text T, and (iv) the query q formalizes the question Q, then the solver’s answer is correct for T and Q.

sound(S) ∧ equisat(F′, F) ∧ faithful(F, T) ∧ formalizes(q, Q)  →  correct(S(F′), T, Q)
(6.1)

The schema is deliberately flat. It names four things that can each be false, and the symbolic pipeline touches only the first two. The model contributes to (iii) and (iv), certifying neither. Soundness can be checked by proof logging or a verified kernel. Equisatisfiability is a proof obligation about the encoding; Tseitin definitions preserve it only if the auxiliaries are handled correctly. Fidelity is an argument about meaning with no decision procedure. The question is hardest, because a question can be ambiguous in ways the text does not resolve.

Table 6.1 · Who guarantees what. The last column is the part usually missing from the claim.
ComponentClaimGuaranteeChecked by
Proposer (LLM)F is a faithful translation of TNoneHuman review, tests, a second formalization
ParserF′ is well-formedSyntaxThe parser
EncoderF′ is equisatisfiable with FConditional on the encoding argumentA proof or a test
SolverS(F′) is correct for F′Sound; complete for the fragmentThe solver, a proof log, a kernel
CheckerThe artifact satisfies F′MechanicalAn evaluator or a validator
Humanq is the questionNoneReview

Three distinctions that are easy to lose

A model is not a proof of the query. If the query is true in the returned model, the pipeline has found a world where it holds — not a proof that it holds in every world. Entailment is the universal quantifier over models.

UNSAT is not “no.” If F ∧ ¬q is unsatisfiable, the answer is “yes, q follows.” If F itself is unsatisfiable, the answer is “everything follows,” a bug in the formalization. The two cases look the same to a pipeline that records only the solver’s status.

A checked proof is not a checked statement. A proof assistant checks that the proof term has the type of the stated theorem, not that the theorem is the English claim. AlphaGeometry’s engine checks the proof, not the formal statement. Lean’s kernel checks the term; the statement and axioms are the specification (de Moura et al., “The Lean Theorem Prover,” CADE-25, 2015).

The sentence to remember

The solver guarantees a theorem about the formalization. The language model only proposes the formalization. The guarantee is relative to the formalization, and the formalization is the unverified part.

This is not a reason to abandon the interface. A solver-backed pipeline can be far more reliable than free-form generation, because most errors are formalization errors a careful check can catch, and a solver never hallucinates a proof step. The gain is real. The claim that the system “cannot be wrong” is not.

07 / CasesFour systems, one anatomy.

The cases are different domains with the same anatomy: a model produces a formal object, an oracle decides something about it, and a check closes the loop. For each, ask what is checked and what is assumed.

AlphaGeometry: proposals plus deduction

The model proposes auxiliary constructions — the extra points and lines that make a geometry proof go through — and a symbolic deduction engine closes the proof. The paper reports 25 of 30 IMO-level geometry problems solved within the olympiad time limit (Trinh et al., Nature, 2024, DOI 10.1038/s41586-023-06747-5). The proof is a formal object and the engine checks it; the unverified part is the formal statement.

LLM+P: translation plus a planner

The model writes PDDL and a classical planner returns a plan correct or optimal for it. The paper reports optimal solutions for most benchmark problems, while the model alone fails to produce feasible plans for most (arXiv:2304.11477). The guarantee is relative to the PDDL model; a missing precondition can make a plan valid in PDDL and wrong in the world.

PAL: translation plus an interpreter

The model writes a program and a Python interpreter executes it. On GSM8K the paper reports a 15-point absolute top-1 gain for Codex with PAL over PaLM-540B with chain-of-thought (arXiv:2211.10435). The interpreter guarantees the output is the program’s output, not that the program is the right one; that is a specification question.

Logic-LM: translation plus a solver plus repair

The model translates a problem into a symbolic formulation, solves it, and uses solver errors to refine the formulation. The reported average gain is 39.2% over standard prompting and 18.4% over chain-of-thought across five datasets (arXiv:2305.12295). Refinement only reacts to errors the solver can see; a satisfiable, wrong formulation produces no error message.

Table 7.1 · The four cases along the tuple. “Unverified” is the part the guarantee does not cover.
SystemModel’s roleOracleChecked artifactUnverified
AlphaGeometryPropose auxiliary constructionsDeduction engineProofThe formal statement
LLM+PWrite PDDLClassical plannerPlanThe PDDL domain
PALWrite a programPython interpreterProgram outputThe program’s specification
Logic-LMWrite a formulationSAT/SMT solverAnswer + solver statusThe formulation

PlanBench is the counterweight: on planning domains from the automated-planning community, plan generation falls short even for state-of-the-art models (arXiv:2206.10498). The interesting capability appears when the model is paired with a planner.

Source note · on the numbers

The percentages above are the numbers reported by the papers, on their benchmarks. They are not independent replications, and they are not guarantees. The architecture is the lesson; the number is a datapoint about a particular benchmark, model, and prompt.

08 / RecapWhat you should be able to do now.

01

Draw the loop and name its two different checks.

02

Explain why a solver’s guarantee is relative to the formalization, not the text.

03

Formalize “only if,” “unless,” and quantifier scope, and name the error each invites.

04

Distinguish a SAT model from entailment, and explain why an unsat premise set entails everything.

05

Say which solver output is self-certifying and which requires a proof or trust.

06

Name the three failure families: formalization, solver, leakage.

07

State the four antecedents of the guarantee schema, and the hard one.

08

Read a system such as Logic-LM, LLM+P, PAL, or AlphaGeometry along the tuple.

Exercises

  1. Break the three boxes. In the lab, run the three candidates and record the model, answer, and one-literal difference. Then construct a fourth candidate whose change is not a single literal.
  2. Formalize the alibi. “Unless the power failed, the camera was recording. The camera was not recording.” Write the faithful formula, the converse, and the reversal of “unless”; say what each entails, then check by enumerating four assignments.
  3. Find the missing axiom. In the wet-pavement puzzle, the faithful formula leaves the rain undetermined. Add one premise that makes rain entailed and one that makes it refuted. Which is the more plausible reading?
  4. Design a leakage test. Take a small puzzle benchmark and write three perturbations a memorizing model would fail: renamed constants, permuted premises, replaced vocabulary. Which is hardest to survive without formalizing?
  5. Audit a pipeline. Pick a system from §7. Draw its loop, mark the internal check, the external check, and the trust base, then write the claim it is entitled to make and the one it is not.
  6. Argue the other side. Write the strongest case that a solver-backed pipeline is not worth the complexity, then the strongest case for it. Which evidence would change your mind?

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 five are the spine; the rest are the next layer.

Language

LLM+P: Empowering Large Language Models with Optimal Planning Proficiency

Liu et al. · 2023 · PDDL plus a classical planner

Planning

LLMs Can’t Plan, But Can Help Planning in LLM-Modulo Frameworks

Kambhampati et al. · ICML 2024 · the generator–critic position

Framing

PAL: Program-aided Language Models

Gao et al. · ICML 2023 · code as the intermediate step

Code

ReAct: Synergizing Reasoning and Acting in Language Models

Yao et al. · ICLR 2023 · tools in the loop

Agents

PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change

Valmeekam et al. · NeurIPS 2023 Datasets & Benchmarks · negative control

Evaluation

Solving olympiad geometry without human demonstrations

Trinh et al. · Nature 2024 · proposals plus deduction

Math

Faith and Fate: Limits of Transformers on Compositionality

Dziri et al. · NeurIPS 2023 · why depth is hard

Limits

Chain-of-Thought Prompting Elicits Reasoning in Large Language Models

Wei et al. · NeurIPS 2022 · the loop’s baseline

Prompting

Self-Consistency Improves Chain of Thought Reasoning in Language Models

Wang et al. · ICLR 2023 · sampling versus checking

Prompting
Source note · on the figures

Figure 1.1 is a schematic drawn for this lecture, not a reproduction. The citations identify the systems and the reported results; the drawing is ours. The percentages in §2 and §7 are those reported in the cited abstracts, labelled as reported results rather than independent measurements.