Lecture 06 · Act III · The five interfaces

A comparative framework.

Expressivity, complexity, guarantees. Two systems can share the label and share nothing else. The difference is a tuple you can fill in.

28 slides 6 case studies 1 selector Self-paced
00 · Learning objectivesLecture 06 · A comparative framework

By the end of this lecture

Four moves, one instrument.

01 · Compare

Fill the tuple

Representation, inference, coupling, guarantee — then supervision, cost, data efficiency, transparency.

02 · Express

Explain expressivity

Language, model, and system expressivity; the 1-WL ceiling on message passing.

03 · Cost

Read the ladder

Data vs combined, decision vs counting, worst case vs runtime — and what the class does not say.

04 · Audit

Separate guarantees

Empirical, sound, complete, calibrated, certified, safe, conformal; name the assumption.

S/V · Lecture 06
00 · The hookLecture 06 · A comparative framework

One instruction · “Put the red cube in the box without touching the lamp”

One task, three architectures.

A · end-to-end

Policy

Pixels and instruction in, motor commands out. No object list, no plan, no lamp model.

GUARANTEE · empirical

B · pipeline

Perceive → plan

Detector, scene graph, PDDL, planner, controller. The plan is a proof-like object.

GUARANTEE · plan validity, given the model

C · proposal + check

Verify → act

Model proposes a plan; a verifier checks preconditions; a shield refuses unsafe actions.

GUARANTEE · checked actions, given the spec

The three are not ranked. B has the strongest guarantee and the most ways to fail before it applies. C fails more gracefully. A is cheapest to build and hardest to audit.

S/V · Lecture 06
00 · The hookLecture 06 · A comparative framework

The comparison, in four slots

The label is a region. The tuple is a position.

Representation

What can be denoted? Atoms, relations, programs, graphs, vectors. What is explicit, and what is left in weights.

Inference

What reasoning is supported? Deduction, induction, abduction; exact or approximate; the actual procedure.

Coupling

Where does information cross? Pipeline, nested, joint, tool use; what is passed, and in which direction.

Guarantee

What is promised? Empirical, sound, complete, calibrated, certified, safe — and under which assumptions.

Then add four operational axes: supervision, cost, data efficiency, transparency. The first four say what the system is; the last four say what it takes to build and trust it.

S/V · Lecture 06
01 · The axesLecture 06 · A comparative framework

Eight questions that separate systems

The comparison table.

AxisThe questionWhat to look for
RepresentationWhat can it denote?Atoms, relations, programs, graphs, vectors; explicit vs in weights
InferenceWhat reasoning?Deduction, induction, abduction; exact or approximate; procedure
CouplingWhere does it cross?Pipeline, nested, joint, tool use; direction; what is passed
GuaranteeWhat is promised?Empirical, sound, complete, calibrated, certified, safe
SupervisionWhat is labeled?Full, weak, QA pairs, demonstrations, programs, none
CostWhat does it consume?Training, latency, solver calls, memory, engineering
Data efficiencyHow much per competence?Examples per concept; transfer; whether symbols supply a prior
TransparencyWhat can be inspected?A symbol, a trace, a proof, a probability; or only post-hoc
S/V · Lecture 06
01 · The axesLecture 06 · A comparative framework

Why the eight axes trade off

Three lenses, not three more rows.

01 · Expressivity

Buys distinctions

What the language can state at all. More resources, more properties — including false ones.

02 · Complexity

Sets the price

What deciding those distinctions costs in the worst case. A class is a cliff, not a clock.

03 · Guarantee

Makes the promise

What survives when the worst case happens — and which assumption the promise rests on.

A comparison that stops at the tuple can still be fooled. The lenses force the follow-up: which fragment, which procedure, which assumption?

S/V · Lecture 06
02 · ExpressivityLecture 06 · A comparative framework
02 / 08

What a language can say at all.

Before data, before training, before the benchmark: does the vocabulary have the resources to state the difference?

S/V · Lecture 06
02 · ExpressivityLecture 06 · A comparative framework

A word that hides three questions

Language, model, system.

Language

What the formalism states

Propositional, Datalog, ALC, first-order, ASP. The grammar and its restrictions.

Model

What the network discriminates

A GNN is bounded by 1-WL. A transformer is a different family with a different ceiling.

System

What the assembly decides

A symbolic readout can answer a query no GNN alone can learn. The interface adds expressivity.

The language sets an upper bound; the system decides how much is usable. A first-order knowledge base restricted to Horn clauses can be less expressive in practice than a well-chosen Datalog program.

S/V · Lecture 06
02 · ExpressivityLecture 06 · A comparative framework

The fragment ladder · schematic, not to scale

More resources, more distinctions, more restrictions.

LANGUAGE WHAT IT CAN EXPRESS ANCHOR Propositional atoms · Boolean connectives SAT · NP-complete Datalog relations · joins · recursion · least fixpoint PTIME (data) ALC concepts · roles · existential / universal restrictions ExpTime-complete FOL quantifiers · functions · arbitrary relations undecidable ASP default negation · stable models · disjunction NP-hard 1-WL ceiling
Schematic. The vertical order follows representational resources; the anchors are worst-case classes, not a ranking of usefulness. ASP adds default negation, a different resource, not a higher rung. The teal bracket is the 1-WL ceiling, discussed next.
S/V · Lecture 06
02 · ExpressivityLecture 06 · A comparative framework

A ceiling on one neural family, stated carefully

Two graphs a message-passing network cannot tell apart.

BOTH GRAPHS: 6 NODES, EVERY NODE OF DEGREE 2 C6 · one cycle 2K3 · two triangles same 1-WL colours A symbolic query, a higher-order message, or a structural feature can separate them.

Message-passing networks that aggregate neighbourhood features are at most as discriminative as 1-WL colour refinement (Xu et al., arXiv:1810.00826; Morris et al., arXiv:1810.02244). This is a claim about graph discrimination with fixed features — not about all tasks, transformers, or global readout.

S/V · Lecture 06
03 · ComplexityLecture 06 · A comparative framework

The bill for the distinctions

Four distinctions keep the claims honest.

Decision · search · counting

Does a model exist, find one, count them all. Different problems, different classes.

Data · combined

Fix the program and grow the database, or grow both. The PTIME claim is the former.

Worst case · typical

A class is an upper bound, not a latency. NP-hard instances can be small and structured.

Exact · approximate

An approximation can move a problem down the ladder and change the guarantee at once.

The interface changes the bill. A verifier per episode is not a verifier per token; a weighted model count inside the forward pass pays a #P-hard price in the worst case.

S/V · Lecture 06
03 · ComplexityLecture 06 · A comparative framework

Worst-case inclusions · schematic, not a runtime chart

The ladder, with its side lane.

WORST-CASE COST · NOT TO SCALE P NP PSPACE ExpTime UNDEC. Datalog · PTIME in data complexity SAT · NP-complete · normal ASP · NP-complete STRIPS plan existence · PSPACE-complete ALC concept satisfiability · ExpTime-complete First-order validity · undecidable #P exact probabilistic inference counting, not decision Inclusions are worst case. A small NP-hard instance can beat a large PTIME one.
S/V · Lecture 06
03 · ComplexityLecture 06 · A comparative framework

What the ladder does not say

A class is a cliff, not a clock.

NP-hard ≠ slow

Structure in real instances is why SAT and ASP solvers work. The label describes the worst case, not your case.

PTIME ≠ fast

Quadratic on a billion-edge graph is not a product feature. Constants, memory, and I/O count.

Class ≠ system

The interface multiplies cost by calls. Count the calls per episode or per token before ranking two systems.

Budget the interface, not just the solver. An exact solver with a timeout is an anytime method; “sound unless it times out” is weaker than “sound”.

S/V · Lecture 06
04 · GuaranteesLecture 06 · A comparative framework

A promise with a footnote

Seven claims, seven assumptions.

ClaimWhat is assertedWhat it assumesWhat it does not buy
EmpiricalA metric on a test distributionThe test resembles deploymentAnything off-distribution
SoundNo false positives relative to the modelFormalization and checker are correctCompleteness
CompleteNo false negatives; every entailment returnedTermination and resourcesSoundness on its own
CalibratedConfidence matches observed frequencyExchangeability or a calibration setCorrectness; robustness
CertifiedA proof checked by a trusted checkerChecker, statement, encodingThe intended property, if misstated
SafeActions stay inside a safe setThe monitor’s model and sensorsSafety outside the set
ConformalMarginal coverage at least 1 − αExchangeable calibration and test dataConditional coverage; correctness
S/V · Lecture 06
04 · GuaranteesLecture 06 · A comparative framework

Every formal claim is a chain

The guarantee is only as strong as the weakest link.

intended property what you mean formal statement what you wrote encoding what the tool sees solver / checker what decides result what you claim THE SPECIFICATION GAP usually the weakest link

A verified system is correct relative to a specification. If the specification is incomplete, the verification is a proof about the wrong theorem. If the encoding is wrong, the proof does not transfer.

S/V · Lecture 06
04 · GuaranteesLecture 06 · A comparative framework

Where the footnote bites

Three ways a guarantee fails.

01 · Specification

The wrong theorem

The formal statement misses the intended property. The proof is valid and irrelevant. This is the most common failure and the hardest to see.

02 · Monitor

The wrong world

A shield enforces a safe set defined by a sensor model. If the model is wrong, the shield is sound and useless.

03 · Calibration

The wrong confidence

Calibration says 0.8 means 80%, not that 0.8 is correct. It does not survive distribution shift without re-fitting.

“Verified” is not a synonym for “correct”. It means correct relative to a statement, checked by something, under assumptions. Name all three.

S/V · Lecture 06
05 · Design patternsLecture 06 · A comparative framework
05 / 08

The shape of the coupling.

Pipeline, nested, joint, tool use. The pattern decides the training signal and the failure mode.

S/V · Lecture 06
05 · Design patternsLecture 06 · A comparative framework

Four answers to “where does the guarantee come from?”

Pipeline · nested · joint · tool use.

01 · Pipeline

A → B → C

Perception, symbolization, reasoner, actuator. Stages trained separately. The guarantee is stage-local; errors compound.

02 · Nested

Logic inside the graph

A symbolic executor inside the network, or neural predicates inside a program. Exact or approximate relative to the program; inference cost.

03 · Joint

One loss, two terms

Data term plus logic term, trained end-to-end. A soft constraint; no hard guarantee. λ has a semantic effect.

04 · Tool use

Propose, call, repair

Model emits a formal artifact; a solver checks it; errors feed back. The guarantee is checker-relative; translation errors sit outside.

S/V · Lecture 06
05 · Design patternsLecture 06 · A comparative framework

What the diagram hides

Four anti-patterns.

Anti-patternWhat it looks likeThe test
Symbolic decorationA logic layer that never changes the answer; a checker always satisfiedRemove it. Does any output change?
Guarantee launderingAn empirical result described as “safe” or “verified”Name the formal statement and the checker
Model captureThe verifier’s specification is fitted to the model it checksWho wrote the spec, and on what data?
Interface explosionSix learned stages and five hand-written translationsCount the interfaces and their owners

Each interface needs an owner, a test, and a stated assumption. If a component has none of the three, it is a liability in the diagram.

S/V · Lecture 06
06 · SelectionLecture 06 · A comparative framework

From requirements to a shortlist

The first question is the guarantee.

property P must hold for every output Must P hold for every output? no loss / architecture / data choose by supervision and budget yes Is the symbolic model trusted? no loss or data + validation do not hard-constrain yes Can a checker decide P cheaply? yes verifier (runtime) or search (offline) no search with a sound checker or architecture on a fragment rank the shortlist cost · supervision · transparency · the claim
S/V · Lecture 06
06 · SelectionLecture 06 · A comparative framework

The procedure in five steps

Write the claim before the evaluation.

  1. State the requirement as a predicate. “Safe” is not a predicate.
  2. Classify the data and the symbolic model. Trusted, partly, or suspect.
  3. Decide what the symbol is for. Loss, architecture, data, search, verifier.
  4. Budget the interface. Calls, data, latency, fallback.
  5. Write the claim before the evaluation. Guarantee, benchmark, ablation, assumption.
RequirementFirst choice
P must hold; cheap checkerVerifier
P must hold; expensive checkerSearch + certificate
No hard P; weak labelsLoss
Structured data; stable schemaData
End-to-end gradients; programArchitecture
Low compute; no solverLoss or data

Four evaluations: ablate the symbol, stress the composition, audit the guarantee, account for cost.

S/V · Lecture 06
06 · SelectionLecture 06 · A comparative framework

Interactive · a compact version of the lab

Change the requirement. Watch the shortlist move.

Data type
Guarantee
Compute budget

Supervision fixed at weak; trust fixed at partly. The full lab has all five inputs.

RequirementWhat it pushes up
PerceptionArchitecture or loss: the network has to meet the symbols.
GraphData: the structure is the input.
ActionSearch or verifier: the output must be checked.
A required guaranteeVerifier, then architecture; never a soft loss alone.
A low budgetLoss or data; exact inference and search are expensive.

The ranking is a design heuristic, not a guarantee. The lab shows the rule trace.

S/V · Lecture 06
07 · Case studiesLecture 06 · A comparative framework
07 / 08

Six systems, one tuple.

Each puts the guarantee in a different place. Read the rows, then read the assumption the row hides.

S/V · Lecture 06
07 · Case studiesLecture 06 · A comparative framework

Read along the tuple

Same label, different guarantee.

SystemRepresentationInferenceCouplingGuarantee
NS-CLObjects; programsDeductionArchitectureEmpirical
DeepProbLogProbabilistic logicProbabilistic deductionArchitectureEmpirical; exact relative to the program
AlphaGeometryGeometry; rulesDeduction + searchSearchCertified proof
SayCanLanguage; affordancesSequential planningSearch / scoringEmpirical
Logic-LMLanguage → logicDeduction with a solverTool useEmpirical; formal relative to translation
KG reasonerGraph; embeddingsDeduction / inductionDataEmpirical

The strongest guarantee appears where a symbolic engine can check the neural proposal. The weakest appears where the symbolic part is only a constraint on a learned representation.

S/V · Lecture 06
07 · Case studiesLecture 06 · A comparative framework

Two systems, side by side

The same anatomy, a different promise.

NS-CL · vision

The program is the explanation

Objects with attributes → a symbolic program → an answer. Learned from question–answer pairs without program annotations.

GUARANTEE · empirical · caveat: synthetic, closed world

AlphaGeometry · mathematics

The proof is the guarantee

A language model proposes auxiliary constructions; a deduction engine closes the proof. Trained on synthetic data, no human demonstrations.

GUARANTEE · certified · caveat: the formal system

The difference is not the neural part. It is whether the symbolic part can check the proposal, and whether the formal system is settled enough for a proof to mean what you want.

S/V · Lecture 06
07 · Case studiesLecture 06 · A comparative framework

The pattern behind the six rows

Every guarantee is conditional on something the tuple does not show.

01 · Location

Where it lives

The program trace, the program semantics, the proof, the value function, the solver, or the graph. The tuple tells you where to look.

02 · Assumption

What it assumes

A closed world, correct axioms, a formal system, calibration, a faithful translation, or a stable schema.

03 · Weak link

What to audit

The link that carries the claim. Name it before the benchmark, and test it separately from the neural part.

A comparison that stops at “neurosymbolic” stops before the interesting part. The interesting part is the assumption.

S/V · Lecture 06
08 · RecapLecture 06 · A comparative framework

What you should be able to do

Four moves, one instrument.

Compare

Fill the tuple and the four operational axes. Say where the guarantee lives.

Explain

Separate language, model, and system expressivity. State the 1-WL ceiling correctly.

Read

Use the complexity ladder with its qualifications: data vs combined, decision vs counting, worst case vs runtime.

Audit

Distinguish empirical, sound, complete, calibrated, certified, safe, and conformal claims — and name the assumption.

The one sentence: compare systems by what they can represent, what they compute, what it costs, and what is guaranteed — never by the label.

S/V · Lecture 06
08 · RecapLecture 06 · A comparative framework

Next · hands-on

Rank the five interfaces yourself.

Open the selector. Change one requirement at a time. Read the rule trace, not just the top row — the trace is the argument.

Lab 06 · Interface selector → open the lab

S/V · Lecture 06
Speaker notes