Course / Lectures / Act III · The five interfaces Lecture 06

A comparative framework: expressivity, complexity, guarantees.

Two systems both call themselves neurosymbolic. One is a pipeline; one is a proof. The difference is not a label. It is a tuple: what they represent, what inference they support, what it costs, and what — if anything — is guaranteed.

~45 min read 8 sections 6 case studies 1 selector lab Updated 2026-11-16

Ask two engineers whether their system is neurosymbolic and both will say yes. Ask what their system can represent, what it computes, what it costs, and what it guarantees, and the answers may have nothing in common. The label is a region of design space, not a family tree. This lecture replaces the label with a tuple you can fill in.

00 / The hookOne task, three architectures.

Consider a tabletop robot with one instruction: “Put the red cube in the box without touching the lamp.” The task is small enough to describe completely and rich enough to expose every design choice. Three stylized architectures solve it differently.

System A is an end-to-end vision-language-action policy. One network maps image and instruction to motor commands. It has no object list, no plan, and no model of the lamp beyond its weights. Its representation is a vector; its inference is a forward pass; its coupling is none. Its guarantee is empirical.

System B is a pipeline. A detector produces a scene graph; a translator turns it into a PDDL problem; a planner returns actions; a controller executes them. The symbolic part is a real knowledge base. Its guarantee is conditional: if the detector is right, the translation faithful, and the planner sound, the plan works. If any fails, the plan can be valid and useless at once.

System C is a hybrid. A language model proposes a plan; a verifier checks each step against preconditions and a safety specification; a shield refuses forbidden actions; on failure, the model repairs and retries. The guarantee is narrower than B’s and stronger than A’s: every executed action has passed a check, relative to the specification and the monitor’s world model.

Table 0.1 · Three architectures for one instruction. The rows are the comparison; the labels are not.
QuestionA · end-to-end policyB · perception → plannerC · proposal → check
What does it represent?Pixels and proprioception as vectorsObjects, predicates, a goal formulaObjects, a plan, a safety predicate
What inference?Reactive mappingDeduction over a model, plus searchProposal, then deductive checking
Where is the coupling?NonePipeline: detector → translator → plannerTool use: model calls a checker
What is guaranteed?Nothing formalPlan validity, given the modelChecked actions, given the specification
What is the weak link?Distribution shiftPerception and translationThe specification and the monitor

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. A comparison that begins with “which one is neurosymbolic?” cannot see any of this.

Definition · the comparison tuple

Compare two systems by filling four slots: representation (what can be denoted), inference (what reasoning is supported, and by what procedure), coupling (where information crosses), and guarantee (what is promised, under which assumptions). Then add four operational axes: supervision, cost, data efficiency, and transparency.

Caveat · the three systems are stylized

They are not implementations and carry no benchmark numbers. Real systems mix the rows: a VLA policy can call a planner, and a planner can use a learned heuristic. The table is a way to ask questions, not a taxonomy.

01 / The axesEight questions that separate systems.

The first four axes are the tuple. They are descriptive: they say what the system is. The next four are operational: they say what it takes to build, run, and trust. A paper can be strong on one axis and silent on another; silence is information.

Table 1.1 · The eight axes. The first four are the tuple; the last four are the budget.
AxisThe questionWhat to look for
RepresentationWhat can the system denote?Atoms, relations, programs, graphs, vectors; what is explicit vs in weights.
InferenceWhat reasoning does it support?Deduction, induction, abduction; exact or approximate; procedure and termination.
CouplingWhere does information cross?Pipeline, nested, joint, tool use; direction; what is passed.
GuaranteeWhat is promised?Empirical, sound, complete, calibrated, certified, safe; and the assumptions.
SupervisionWhat is labeled?Full, weak, QA pairs, demonstrations, program annotations, or none.
CostWhat does it consume?Training compute, latency, solver calls, memory, engineering time.
Data efficiencyHow much supervision per competence?Examples per concept; transfer; whether symbols supply a prior.
TransparencyWhat can a human inspect?A symbol, a trace, a proof, a probability; or only a post-hoc explanation.

The axes are not independent. A more expressive representation usually makes inference harder. A stronger guarantee usually requires a tighter coupling and a more expensive checker. Weak supervision pushes you toward a loss or an architecture that propagates gradients, not a pipeline that needs labels at every stage.

Three lenses, not three more rows

Expressivity asks what distinctions the language can draw at all. Complexity asks what those distinctions cost in the worst case. Guarantee asks what survives when the worst case happens. They are linked: expressivity buys distinctions, complexity is the price, and a guarantee is a promise that the price was paid under stated assumptions. Two systems can both say “first-order logic” and use fragments with wildly different costs; two can both say “verified” and mean a proof object versus a unit test.

Source note · on taxonomies

The boxology literature proposes compositional patterns rather than a hierarchy (van Harmelen & ten Teije, arXiv:1905.12389). De Raedt et al. organize the space between the fields (arXiv:2003.08316); Besold et al. survey the earlier tradition (arXiv:1711.03902). Kautz’s NeSy 2024 taxonomy and the Garcez–Lamb “third wave” framing cut it differently (DOI 10.1007/s10462-023-10448-w). The eight axes are a teaching device, not a consensus.

02 / ExpressivityWhat a language can say at all.

Expressivity is the first lens because it is prior to data and prior to training. If a language cannot distinguish two worlds, no amount of supervision will make a model trained in that language distinguish them. The question is not “is this model smart enough?” but “does its vocabulary have the resources to state the difference?”

The standard ladder runs from propositional logic to first-order logic, with several fragments in between. Each rung is a set of representational resources: atoms, relations, recursion, quantifiers, functions, negation. Each rung is also a set of restrictions. The art of knowledge representation is choosing the weakest language that can still state the property you need. ASP is not a rung above first-order logic: default negation is a different resource.

Table 2.1 · A fragment ladder. The right column is a complexity anchor, not a score.
LanguageWhat it can expressWhat it does not give youAnchor
Propositional logicBoolean combinations; truth tablesObjects, relations, quantifiersSAT is NP-complete
DatalogRelations, joins, recursion, a least fixpoint; transitive closureFunction symbols, counting, unstratified negationPTIME (data)
Description logic (ALC)Concepts, roles, negation, existential and universal restrictionsn-ary relations, counting, recursionExpTime-complete
First-order logicQuantifiers, arbitrary relations and functionsA general decision procedureUndecidable
Answer set programmingDefault negation, stable models, disjunctionA unique model; polynomial worst caseNP-hard
Message-passing GNNNode and edge features; local aggregationDistinctions beyond 1-WL; global structureBounded by 1-WL
A schematic expressivity ladder from propositional logic to first-order logic Four classical fragments plus one different resource. Propositional logic has the fewest representational resources; Datalog adds relations and recursion; description logic adds concepts and roles; first-order logic adds quantifiers and functions. Answer set programming adds default negation and stable models, a different resource rather than a higher rung. The ordering is not a total order of usefulness, and complexity rises unevenly. A separate bracket marks the 1-WL ceiling on message-passing graph networks. MORE RESOURCES SCHEMATIC · NOT TO SCALE FOL quantifiers · functions · arbitrary relations undecidable ASP default negation · stable models · disjunction NP-hard ALC concepts · roles · existential / universal ExpTime Datalog relations · joins · recursion PTIME (data) Prop. atoms · Boolean connectives NP-complete 1-WL ceiling on message passing The bars encode representational reach, not usefulness. A weaker language with a sound solver can beat a stronger one.
Fig. 2.1 A schematic ladder, not a measurement. The vertical order follows representational resources; the right-hand labels are worst-case anchors and do not rise monotonically with the bars. ASP adds a different resource, not a higher rung. The teal bracket is the 1-WL ceiling on message passing.

Three things are often called “expressivity”, and conflating them causes bad comparisons. Language expressivity is what the formalism can state. Model expressivity is what the network or solver can represent. System expressivity is what the whole assembly can state and decide, including the interface. A GNN with a symbolic readout can answer a query no GNN alone can learn; a first-order knowledge base used through a tiny Horn fragment may be less useful in practice than a well-chosen Datalog program. The language sets an upper bound; the system decides how much is usable.

The 1-WL ceiling, stated carefully

Message-passing graph networks that aggregate neighbourhood features are at most as discriminative as 1-dimensional Weisfeiler–Lehman colour refinement (Xu et al., arXiv:1810.00826; Morris et al., arXiv:1810.02244). This concerns distinguishing non-isomorphic graphs with the same initial features. It does not say GNNs cannot solve a task, and it does not cover transformers or global readout. It is a ceiling on one family, and it explains why structural features, higher-order messages, or a symbolic query are sometimes the only way to express the distinction.

The blind spot is easy to see: a six-cycle and two disjoint triangles are both 2-regular on six nodes. With identical features, colour refinement stops, and a message-passing network with a permutation-invariant readout cannot separate them. A symbolic query, a higher-order message, or a structural feature can.

Caveat · expressivity is not a score

“More expressive” sounds like “better”. It is not. A more expressive language can state more properties, including more false ones, and it usually makes entailment harder and learning less data-efficient. State the distinction the task needs, then choose the weakest language that can state it; every added resource is a promise to pay in inference, supervision, or both.

03 / ComplexityWhat the distinctions cost.

Complexity is the second lens because it is the bill for the first. The ladder in §2 is a ladder of representational resources; the ladder in this section is the price of deciding questions in those languages. The two ladders do not line up neatly, and that is exactly why a comparison needs both.

Four distinctions keep the claims honest. Decision versus search versus counting: deciding whether a model exists, finding one, and counting all of them have different classes. Data versus combined complexity: fixing the program and growing the database is not the same as growing both. Worst case versus typical case: a class is an upper bound, not a latency prediction. Exact versus approximate: an approximation can move a problem down the ladder and change the guarantee.

Table 3.1 · The complexity ladder, stated precisely, with the original results.
ProblemPrecise statementWhat it assumes
Propositional satisfiabilitySAT is NP-complete (Cook, 1971; Levin, 1973)Propositional clauses; formula size is the input
Datalog evaluationPTIME-complete in data complexity (Vardi, 1982); EXPTIME-complete combinedThe program is fixed for the data-complexity claim
Answer set programmingNormal programs: NP-complete; general ASP: NP-hard; disjunctive: Σ2P-complete (Eiter & Gottlob, 1995)Propositional programs; stable-model semantics
Description logic ALCConcept satisfiability is ExpTime-complete (Schild, 1991)TBox and ABox; binary roles
STRIPS planningPlan existence is PSPACE-complete (Bylander, 1994)Propositional STRIPS; plan length unbounded
First-order logicValidity and satisfiability are undecidable (Church, 1936; Turing, 1936)Full first-order syntax; no fragment
Probabilistic inferenceExact is #P-hard (Roth, 1996); approximate is NP-hard (Dagum & Luby, 1993)General network structure; exact counting
A schematic complexity ladder with a side lane for counting From bottom to top: P contains Datalog evaluation in data complexity; NP contains propositional satisfiability and normal answer set programming; PSPACE contains STRIPS plan existence; ExpTime contains ALC concept satisfiability; full first-order logic is undecidable. A separate dashed lane on the right holds #P, for exact probabilistic inference, which is a counting class rather than a rung in the decision ladder. The vertical axis is worst-case cost, not runtime. WORST-CASE COST · SCHEMATIC P NP PSPACE ExpTime UNDEC. Datalog · PTIME in data complexity SAT · NP-complete · ASP (normal) · 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 be faster than a large PTIME one.
Fig. 3.1 A schematic of worst-case inclusions, not a runtime chart. #P is a counting class, so it sits in a side lane. Datalog’s PTIME label is data complexity; combined complexity is higher. Citations for each rung are in Table 3.1.

Reading the ladder without misreading it

An NP-complete label does not mean “too slow”: modern SAT solvers handle instances with millions of clauses when the instances have structure. A PTIME label does not mean “fast”: a quadratic algorithm on billions of edges is not a product feature. The ladder says what to expect as the input grows and where the cliff is, not how long today’s job will take.

The interface changes the accounting. A verifier called once per episode costs differently from one called per token. A probabilistic logic program that performs weighted model counting inside the forward pass pays a #P-hard price in the worst case, which is why practical systems restrict the program, compile it, or approximate it. The number and size of calls are the rest of the bill.

Two consequences follow. A tractable fragment with a sound solver often beats a general language with a heuristic; an exact solver with a timeout is an anytime method, so “sound unless it times out” is weaker than “sound”.

Caveat · the ladder is not a total order of systems

NP, PSPACE, ExpTime, and undecidable are worst-case classes under standard assumptions; #P is a counting class. Systems also differ in the size of the encoding, the number of solver calls, the quality of the heuristic, and the distribution of instances. A comparison that ranks two systems by the complexity class of their symbolic language alone is as incomplete as one that ranks them by their labels.

04 / GuaranteesWhat a claim actually buys.

A guarantee is a promise with a footnote. The promise is the property; the footnote is the assumption. Most disagreements are about the footnote, not the property. The taxonomy below separates the promises; most systems live in the first row, and the problem begins when that row is paraphrased as a formal claim.

Table 4.1 · A guarantee taxonomy. Each row names the assumption that makes the claim true.
ClaimWhat is assertedWhat it assumesWhat it does not buy
EmpiricalA metric on a test distributionThe test resembles deployment; the metric measures the taskAnything off-distribution
SoundNo false positives relative to the model: if it says yes, the entailment holdsThe formalization, semantics, and checker are correctCompleteness; every true answer
CompleteNo false negatives: every entailed answer is returnedTermination and resource bounds; soundness if correctness is claimedSoundness on its own; speed
CalibratedPredicted confidence matches observed frequencyExchangeability or a representative calibration setCorrectness; robustness to shift
CertifiedA proof or certificate is checked by a trusted checkerThe checker, the formal statement, the encodingThe intended property, if the statement is wrong
Safe / shieldedExecuted actions stay inside a safe setThe monitor’s model of safety and the sensorsSafety outside the set; monitor error
ConformalMarginal coverage at least 1 − αExchangeability of calibration and test dataConditional coverage; correctness

Soundness and completeness are relative to a model. A sound prover can be wrong about the world if the axioms are wrong; a complete planner can return an invalid plan if the precondition model is incomplete. The pair is a property of the procedure, not the knowledge base. A formal guarantee is always conditional: if the model is right, then the conclusion follows.

Sound:   R(K, φ) = yes  ⇒  K ⊨ φ     Complete:   K ⊨ φ  ⇒  R(K, φ) = yes
(4.1)

Calibration says that when the system reports 0.8, the event happens about 80% of the time. It does not say 0.8 is the right answer, and it does not survive distribution shift without re-calibration. A calibrated model can be consistently wrong.

A certificate is the strongest guarantee here and the most conditional. AlphaGeometry’s model proposes constructions; the deduction engine checks them; the proof is a finite object that can be inspected. The guarantee is not “the model is correct” but “this proof is valid in this system”. If the formal system misses the intended geometry, the proof can be valid and irrelevant. Lean and Coq work the same way: the kernel is trusted, the statement is the user’s.

Shielding and conformal prediction are most often confused with correctness. A shield guarantees that the executed action is in the safe set as the monitor defines it; if the sensor model is wrong, it can be sound and useless. Conformal prediction guarantees marginal coverage over exchangeable data, not per-case coverage and not correctness.

The guarantee chain

Every formal claim has a chain: intended property → formal statement → encoding → solver or checker → result. It is only as strong as the weakest link. The specification gap — the distance between the intended property and the formal statement — is usually the weakest link.

Caveat · “verified” is not a synonym for “correct”

A verified system is correct relative to a specification. If the specification is incomplete, the verification is a proof about the wrong theorem. The word should always be followed by “against what, with what checker, under what assumptions”.

05 / Design patternsThe shape of the coupling.

The coupling is where a neurosymbolic system becomes a system rather than a list of components. Boxology — the study of box-and-arrow diagrams for hybrid systems — forces the arrows to be explicit: what is passed, in which direction, and what happens when the receiver disagrees (van Harmelen & ten Teije, arXiv:1905.12389). Four coarse patterns cover most of the literature.

The five interfaces are not mutually exclusive. A system can use a logic loss during training and a verifier at runtime; a nested architecture can call a search procedure for a subproblem. What matters for comparison is which interface carries the guarantee, and whether the others undermine it. A soft loss followed by a hard verifier is coherent; a verifier whose specification is generated by the model it checks is not.

Table 5.1 · Four coupling patterns. The pattern decides the training signal and the failure mode.
PatternShapeTrainingGuaranteeTypical failure
PipelinePerception → symbolization → reasoner → actuator; one directionStages trained separately, or fine-tuned on reasoner outputsStage-local; end-to-end noneErrors compound; correct reasoning over wrong symbols
NestedSymbolic executor inside the network, or neural predicates inside a programJointly, through a differentiable semanticsExact or approximate relative to the programInference cost; discrete gradients; restricted fragments
JointOne loss with a data term and a logic termEnd-to-end, with a weighting λSoft constraint; no hard guaranteeThe constraint is traded against data; λ has a semantic effect
Tool useModel emits a formal artifact; solver returns a result; loopModel trained separately; solver fixedChecker-relative; translation errors outsideWrong formalization; latency; repair loops

Anti-patterns

Symbolic decoration. A logic layer is added to the diagram but never changes the answer: a checker that is always satisfied, or a program never executed. If removing it changes nothing, it is not an interface.

Guarantee laundering. An empirical result is described with the vocabulary of formal verification. “The shield prevents unsafe actions” is a formal claim; “the shield reduced unsafe actions on the test set” is an empirical one. They require different evidence.

Model capture. The verifier’s specification is learned from the same model it checks, or the monitor’s thresholds are tuned on the test distribution. The guarantee becomes circular.

Interface explosion. Six learned stages and five hand-written translations give six places for an error and five places to hide it.

06 / SelectionFrom requirements to a shortlist.

There is no best interface. There is a best fit between a requirement and an interface, and the fit is usually over-determined: several interfaces satisfy the same requirement at different costs. The procedure below narrows the space to a shortlist and makes the trade-off explicit. It is a filter, not an oracle.

A decision tree from requirements to an interface shortlist Start with the requirement. If a property must hold for every output, ask whether the symbolic model is trusted; if not, use a soft loss or data with validation. If trusted, ask whether a checker can decide the property cheaply; if yes, use a verifier at runtime or a search procedure offline; if no, use a restricted fragment with a sound checker or an architecture. If no property must hold for every output, choose by supervision and budget among loss, architecture, and data. The tree returns a shortlist, not a winner. FROM REQUIREMENT TO SHORTLIST Requirement property P, inputs, assumptions Must P hold for every output? yes no Is the symbolic model trusted? yes no Can a checker decide P cheaply? yes no verifier (runtime) or search (offline) first choice search with a sound checker or architecture on a fragment loss or data do not hard-constrain loss / architecture / data choose by supervision and budget Rank the shortlist by cost, supervision, transparency and write down the claim you can actually defend The tree returns a shortlist, not a winner. The lab in §6.4 makes the rules explicit.
Fig. 6.1 A decision procedure, not a decision theory. The first question is whether a property must hold for every output; the rest are feasibility checks. The interface-selector lab turns the same questions into a scoring rule table.

The five steps

  1. State the requirement as a predicate. “Safe” is not a predicate. “The end effector never enters the region above the stove while the burner is on” is. Write the property, the inputs it quantifies over, and its assumptions.
  2. Classify the data and the symbolic model. Perception, language, graph, or action; then trusted, partially trusted, or suspect. A suspect model should not be a hard constraint.
  3. Decide what the symbolic part is for. A training signal, a computation, a structure, a search, or a check. If the answer is “all of them”, each interface needs its own guarantee.
  4. Budget the interface. Count the calls, the data passed, the latency, and the fallback. A verifier per token and one per episode are different products.
  5. Write the claim before the evaluation. Name the guarantee, the benchmark, the ablation, and the assumption. If the evaluation cannot isolate the interface, it cannot support the claim.
Table 6.1 · A shortlist by requirement. “Avoid” means “not as the only interface”, not “never”.
RequirementFirst choiceSecondAvoid as the only interface
P must hold for every output; a cheap checker existsVerifier at runtimeSearch + certificate offlineLoss alone: a soft penalty is not a guarantee
P must hold; the checker is expensiveSearch + certificateVerifier with caching or a tighter fragmentArchitecture without a checker
No hard requirement; weak supervisionLossArchitecture with differentiable semanticsVerifier: overhead with no requirement
Structured data; stable schemaData (graph, ontology, program)Architecture over the structureSearch with no generator
End-to-end gradients; program semanticsArchitectureLoss on a compiled fragmentPipeline: no gradient path
Low compute; no solver in the loopLoss or dataVerifier with a cheap monitorSearch or exact inference

Four evaluations separate the interface from the rest. Ablate the symbolic part: remove it, weaken it, or shuffle it. If nothing changes, the interface is decoration. Stress the composition: test combinations absent from training. Audit the guarantee: write the chain and test the weakest link. Account for cost: report latency, memory, solver calls, and engineering time, not only accuracy.

Try it · the interface selector

The lab turns this procedure into a deterministic rule base. Choose a data type, a supervision regime, whether a guarantee is required, a compute budget, and whether the symbolic model is trustworthy. The page ranks the five interfaces, shows the rules that fired, and states the trade-off. It is a mirror for your assumptions, not a recommendation engine.

07 / Case studiesSix systems, read along the tuple.

The test of a framework is whether it makes familiar systems look different. The six below are not a leaderboard; they are points in the design space, chosen because each puts the guarantee in a different place. Read each row as a tuple, then read the prose for the assumption the tuple hides.

Table 7.1 · Six systems along the tuple. Cells are qualitative; no benchmark scores are implied.
SystemRepresentationInferenceCouplingGuarantee
NS-CLObject-centric scene; programsDeduction over a sceneArchitectureEmpirical
DeepProbLogProbabilistic logic; neural predicatesProbabilistic deductionArchitectureEmpirical; exact relative to the program
AlphaGeometryGeometry; deduction rulesDeduction + searchSearchCertified proof
SayCanLanguage; skill affordancesSequential planningSearch / scoringEmpirical
Logic-LMLanguage → formal logicDeduction with a solverTool useEmpirical; formal relative to the translation
KG reasonerGraph; embeddings; rulesDeduction / inductionDataEmpirical

NS-CL · the program is the explanation

NS-CL couples a neural object-centric perception module to a symbolic program executor (Mao et al., arXiv:1904.12584). It represents a scene as objects with attributes and relations, deduces over that set, and couples the two architecturally. It learns from question–answer pairs without program annotations, so the program is induced through the interface. The guarantee is empirical and the program trace is inspectable; the caveat is that CLEVR is synthetic.

DeepProbLog · exact semantics, probabilistic cost

DeepProbLog puts neural predicates inside a probabilistic logic program (Manhaeve et al., arXiv:1805.10872). It represents a program with probabilistic facts and neural predicates, performs probabilistic deduction by weighted model counting after compilation, and couples the parts architecturally. The guarantee is exact relative to the program but empirical relative to the world. The tuple hides the cost: exact inference is #P-hard in general, so the practical claim depends on program structure and compilation.

AlphaGeometry · the proof is the guarantee

AlphaGeometry pairs a language model that proposes auxiliary constructions with a symbolic deduction engine that closes the proof (Trinh et al., Nature 2024, DOI 10.1038/s41586-023-06747-5). It represents a formal geometry language, searches over constructions, and couples the model to the engine by search. The guarantee is a proof object, conditional on the formal system and the engine. The model is trained on synthetic data; it is a heuristic, not a source of truth.

SayCan · grounding language in affordances

SayCan combines a language model’s score for a skill with a value function’s estimate that the skill is feasible in the current state (Ahn et al., arXiv:2204.01691). It represents language plus a library of learned skills, plans by scoring skill sequences, and couples the two by search. The guarantee is empirical. The symbolic part is a set of preconditions and affordances, learned or hand-specified; “symbolic” can mean discrete and inspectable, not first-order.

Logic-LM · translation is the interface

Logic-LM asks a language model to translate a problem into a symbolic formulation, calls a solver, and uses the solver’s error messages to repair the translation (Pan et al., arXiv:2305.12295). It represents formal logic, deduces with the solver, and couples them by tool use. The guarantee is empirical overall and formal relative to the translation. The weak link is visible: a sound solver applied to a wrong formalization returns a confident wrong answer. Self-refinement fixes syntax, not misunderstanding.

A knowledge-graph reasoner · structure as data

A knowledge-graph reasoner combines graph embeddings with logical rules (survey: DeLong et al., arXiv:2302.07200). It represents a graph plus an embedding space, performs link prediction or rule application, and couples the parts through data. The guarantee is empirical; the graph is both training signal and knowledge base. The embedding compresses the graph, preserving similarity while losing the relation that matters, and a rule layer inherits the schema’s coverage. The data interface is cheap to deploy and hard to audit.

What the six cases have in common

Each puts the guarantee in a different place: the program trace, the program semantics, the proof, the value function, the solver, or the graph. In every case it is conditional on something the tuple does not show. A comparison that stops at “neurosymbolic” stops before the interesting part.

08 / RecapWhat you should be able to do now.

01

Fill the tuple — representation, inference, coupling, guarantee — then add supervision, cost, data efficiency, and transparency.

02

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

03

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

04

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

05

Recognize the four coupling patterns and the four anti-patterns.

06

Turn a requirement into a shortlist with the five-step procedure, and say what it cannot decide.

07

Read a case study along the tuple and identify the weakest link in its guarantee chain.

08

Write the claim before the evaluation, and design an ablation that isolates the interface.

Exercises

  1. Three architectures, one task. Pick a task you know. Write the three architectures from §0, fill Table 0.1, and mark the row you cannot answer without reading the implementation.
  2. Find the fragment. Take a paper that says “first-order logic” or “knowledge graph”. Identify the actual fragment: quantifiers, arity, recursion, negation. What did the restriction buy?
  3. Audit a guarantee. Take a system that claims “safe” or “verified”. Write the chain and mark the weakest link. If the paper does not give you enough, say what is missing.
  4. Break the selector. In the lab, find two settings that produce the same top interface for different reasons. Read the rule trace: which rule is doing the work?
  5. Cost the interface. Estimate verifier calls in a 1,000-step episode and compare them with one loss evaluation per training batch. What changes?
  6. Argue against the framework. Which pair of systems defeats the eight axes, and what axis would you add?

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 four are the methodological spine of this lecture. The rest are the systems and the background.

A Boxology of Design Patterns for Hybrid Learning and Reasoning Systems

van Harmelen & ten Teije · arXiv:1905.12389 · the pattern vocabulary

Patterns

From Statistical Relational to Neuro-Symbolic Artificial Intelligence

De Raedt et al. · arXiv:2003.08316 · the space between the fields

Survey

Neural-Symbolic Computing: An Effective Methodology for Principled Integration

Garcez, Gori, Lamb, Serafini · arXiv:1905.06088 · the integration programme

Foundations

Neurosymbolic AI: the 3rd wave

Garcez & Lamb · Artificial Intelligence Review 2023 · the framing and its critics

Framing

The Neuro-Symbolic Concept Learner

Mao et al. · ICLR 2019 · the architecture interface, with programs

Vision

DeepProbLog: Neural Probabilistic Logic Programming

Manhaeve et al. · NeurIPS 2018 · exact semantics, probabilistic cost

Logic

Solving olympiad geometry without human demonstrations

Trinh et al. · Nature 2024 · the certified proof

Math

Do As I Can, Not As I Say

Ahn et al. · 2022 · affordances as the grounding

Robotics

Logic-LM

Pan et al. · EMNLP Findings 2023 · translation, solving, repair

Language

Neurosymbolic AI for Reasoning over Knowledge Graphs: A Survey

DeLong, Fernández Mir, Fleuriot · 2023 · the data interface

Knowledge

How Powerful are Graph Neural Networks?

Xu, Hu, Leskovec, Jegelka · ICLR 2019 · the 1-WL ceiling

Expressivity
Source note · complexity and figures

The complexity statements follow the standard results cited in Table 3.1 and Russell & Norvig, Artificial Intelligence: A Modern Approach (4th ed.). Every figure is a schematic; none reproduces a paper figure.