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.
| Question | A · end-to-end policy | B · perception → planner | C · proposal → check |
|---|---|---|---|
| What does it represent? | Pixels and proprioception as vectors | Objects, predicates, a goal formula | Objects, a plan, a safety predicate |
| What inference? | Reactive mapping | Deduction over a model, plus search | Proposal, then deductive checking |
| Where is the coupling? | None | Pipeline: detector → translator → planner | Tool use: model calls a checker |
| What is guaranteed? | Nothing formal | Plan validity, given the model | Checked actions, given the specification |
| What is the weak link? | Distribution shift | Perception and translation | The 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.
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.
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.
| Axis | The question | What to look for |
|---|---|---|
| Representation | What can the system denote? | Atoms, relations, programs, graphs, vectors; what is explicit vs in weights. |
| Inference | What reasoning does it support? | Deduction, induction, abduction; exact or approximate; procedure and termination. |
| Coupling | Where does information cross? | Pipeline, nested, joint, tool use; direction; what is passed. |
| Guarantee | What is promised? | Empirical, sound, complete, calibrated, certified, safe; and the assumptions. |
| Supervision | What is labeled? | Full, weak, QA pairs, demonstrations, program annotations, or none. |
| Cost | What does it consume? | Training compute, latency, solver calls, memory, engineering time. |
| Data efficiency | How much supervision per competence? | Examples per concept; transfer; whether symbols supply a prior. |
| Transparency | What 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.
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.
| Language | What it can express | What it does not give you | Anchor |
|---|---|---|---|
| Propositional logic | Boolean combinations; truth tables | Objects, relations, quantifiers | SAT is NP-complete |
| Datalog | Relations, joins, recursion, a least fixpoint; transitive closure | Function symbols, counting, unstratified negation | PTIME (data) |
| Description logic (ALC) | Concepts, roles, negation, existential and universal restrictions | n-ary relations, counting, recursion | ExpTime-complete |
| First-order logic | Quantifiers, arbitrary relations and functions | A general decision procedure | Undecidable |
| Answer set programming | Default negation, stable models, disjunction | A unique model; polynomial worst case | NP-hard |
| Message-passing GNN | Node and edge features; local aggregation | Distinctions beyond 1-WL; global structure | Bounded by 1-WL |
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.
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.
“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.
| Problem | Precise statement | What it assumes |
|---|---|---|
| Propositional satisfiability | SAT is NP-complete (Cook, 1971; Levin, 1973) | Propositional clauses; formula size is the input |
| Datalog evaluation | PTIME-complete in data complexity (Vardi, 1982); EXPTIME-complete combined | The program is fixed for the data-complexity claim |
| Answer set programming | Normal programs: NP-complete; general ASP: NP-hard; disjunctive: Σ2P-complete (Eiter & Gottlob, 1995) | Propositional programs; stable-model semantics |
| Description logic ALC | Concept satisfiability is ExpTime-complete (Schild, 1991) | TBox and ABox; binary roles |
| STRIPS planning | Plan existence is PSPACE-complete (Bylander, 1994) | Propositional STRIPS; plan length unbounded |
| First-order logic | Validity and satisfiability are undecidable (Church, 1936; Turing, 1936) | Full first-order syntax; no fragment |
| Probabilistic inference | Exact is #P-hard (Roth, 1996); approximate is NP-hard (Dagum & Luby, 1993) | General network structure; exact counting |
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”.
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.
| Claim | What is asserted | What it assumes | What it does not buy |
|---|---|---|---|
| Empirical | A metric on a test distribution | The test resembles deployment; the metric measures the task | Anything off-distribution |
| Sound | No false positives relative to the model: if it says yes, the entailment holds | The formalization, semantics, and checker are correct | Completeness; every true answer |
| Complete | No false negatives: every entailed answer is returned | Termination and resource bounds; soundness if correctness is claimed | Soundness on its own; speed |
| Calibrated | Predicted confidence matches observed frequency | Exchangeability or a representative calibration set | Correctness; robustness to shift |
| Certified | A proof or certificate is checked by a trusted checker | The checker, the formal statement, the encoding | The intended property, if the statement is wrong |
| Safe / shielded | Executed actions stay inside a safe set | The monitor’s model of safety and the sensors | Safety outside the set; monitor error |
| Conformal | Marginal coverage at least 1 − α | Exchangeability of calibration and test data | Conditional 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.
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.
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.
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.
Logic as loss
A differentiable penalty. End-to-end gradients; a satisfied penalty is not a proof.
Logic as architecture
The executor sits inside the computation graph. Exact relative to the program; inference is the price.
Logic as data
Symbols structure the input, output, or embedding. Interpretable, but the embedding can distort.
Logic as search
A proposer generates; a checker accepts. Compositional generalization at the price of search.
Logic as verifier
A monitor checks each action against a specification. Accountability at runtime, as good as the monitor.
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.
| Pattern | Shape | Training | Guarantee | Typical failure |
|---|---|---|---|---|
| Pipeline | Perception → symbolization → reasoner → actuator; one direction | Stages trained separately, or fine-tuned on reasoner outputs | Stage-local; end-to-end none | Errors compound; correct reasoning over wrong symbols |
| Nested | Symbolic executor inside the network, or neural predicates inside a program | Jointly, through a differentiable semantics | Exact or approximate relative to the program | Inference cost; discrete gradients; restricted fragments |
| Joint | One loss with a data term and a logic term | End-to-end, with a weighting λ | Soft constraint; no hard guarantee | The constraint is traded against data; λ has a semantic effect |
| Tool use | Model emits a formal artifact; solver returns a result; loop | Model trained separately; solver fixed | Checker-relative; translation errors outside | Wrong 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.
The five steps
- 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.
- 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.
- 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.
- 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.
- 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.
| Requirement | First choice | Second | Avoid as the only interface |
|---|---|---|---|
| P must hold for every output; a cheap checker exists | Verifier at runtime | Search + certificate offline | Loss alone: a soft penalty is not a guarantee |
| P must hold; the checker is expensive | Search + certificate | Verifier with caching or a tighter fragment | Architecture without a checker |
| No hard requirement; weak supervision | Loss | Architecture with differentiable semantics | Verifier: overhead with no requirement |
| Structured data; stable schema | Data (graph, ontology, program) | Architecture over the structure | Search with no generator |
| End-to-end gradients; program semantics | Architecture | Loss on a compiled fragment | Pipeline: no gradient path |
| Low compute; no solver in the loop | Loss or data | Verifier with a cheap monitor | Search 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.
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.
| System | Representation | Inference | Coupling | Guarantee |
|---|---|---|---|---|
| NS-CL | Object-centric scene; programs | Deduction over a scene | Architecture | Empirical |
| DeepProbLog | Probabilistic logic; neural predicates | Probabilistic deduction | Architecture | Empirical; exact relative to the program |
| AlphaGeometry | Geometry; deduction rules | Deduction + search | Search | Certified proof |
| SayCan | Language; skill affordances | Sequential planning | Search / scoring | Empirical |
| Logic-LM | Language → formal logic | Deduction with a solver | Tool use | Empirical; formal relative to the translation |
| KG reasoner | Graph; embeddings; rules | Deduction / induction | Data | Empirical |
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.
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.
Fill the tuple — representation, inference, coupling, guarantee — then add supervision, cost, data efficiency, and transparency.
Separate language, model, and system expressivity, and state the 1-WL ceiling correctly.
Read the complexity ladder with its qualifications: data vs combined, decision vs counting, worst case vs runtime.
Distinguish empirical, sound, complete, calibrated, certified, safe, and conformal claims — and name each assumption.
Recognize the four coupling patterns and the four anti-patterns.
Turn a requirement into a shortlist with the five-step procedure, and say what it cannot decide.
Read a case study along the tuple and identify the weakest link in its guarantee chain.
Write the claim before the evaluation, and design an ablation that isolates the interface.
Exercises
- 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.
- 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?
- 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.
- 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?
- Cost the interface. Estimate verifier calls in a 1,000-step episode and compare them with one loss evaluation per training batch. What changes?
- 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
From Statistical Relational to Neuro-Symbolic Artificial Intelligence
De Raedt et al. · arXiv:2003.08316 · the space between the fields
Neural-Symbolic Computing: An Effective Methodology for Principled Integration
Garcez, Gori, Lamb, Serafini · arXiv:1905.06088 · the integration programme
Neurosymbolic AI: the 3rd wave
Garcez & Lamb · Artificial Intelligence Review 2023 · the framing and its critics
The Neuro-Symbolic Concept Learner
Mao et al. · ICLR 2019 · the architecture interface, with programs
DeepProbLog: Neural Probabilistic Logic Programming
Manhaeve et al. · NeurIPS 2018 · exact semantics, probabilistic cost
Solving olympiad geometry without human demonstrations
Trinh et al. · Nature 2024 · the certified proof
Do As I Can, Not As I Say
Ahn et al. · 2022 · affordances as the grounding
Logic-LM
Pan et al. · EMNLP Findings 2023 · translation, solving, repair
Neurosymbolic AI for Reasoning over Knowledge Graphs: A Survey
DeLong, Fernández Mir, Fleuriot · 2023 · the data interface
How Powerful are Graph Neural Networks?
Xu, Hu, Leskovec, Jegelka · ICLR 2019 · the 1-WL ceiling
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.