Neurosymbolic AI & Reasoning Models
Combining learning with structured reasoning.
A language model can write a fluent proof with an invalid step in the middle. A theorem prover never takes an invalid step, but it cannot read the problem. Neurosymbolic systems pair the two so that each covers the other's weakness, and this lesson takes apart the main designs and the mathematics that decides when each one works.
What you’ll learn
- Classify a neurosymbolic system by where learning and symbolic reasoning meet: guidance, relaxation, or translation and verification.
- Enumerate programs bottom-up with observational-equivalence pruning, and bound the cost of model-guided enumeration by .
- Relax logical rules with t-norms, compute their gradients, and turn a constraint into a loss by weighted model counting.
- Quantify generate-and-verify and majority voting with pass@ and binomial tails, and explain why a sound checker moves errors into the translation step.
Two kinds of competence
Logic and learning fail in opposite ways. A sound reasoner never draws a conclusion that does not follow from its premises, but someone has to write the premises down, and one missing or mistyped rule breaks it. A trained network absorbs regularities nobody could write down, but it offers only statistical guarantees, and it can fail without warning on inputs unlike its training data.
Neurosymbolic AI builds systems in which each covers for the other. The table is a caricature, but a useful one.
| Property | Learned models | Symbolic reasoners |
|---|---|---|
| Where knowledge comes from | fitted to data | written by people, or derived from written facts |
| What is guaranteed | average accuracy on the training distribution | soundness (sometimes completeness) relative to the premises |
| Inputs unlike the training data | can fail silently | no change, if the premises still hold |
| Noisy or perceptual input | handled naturally | needs clean symbols |
| Cost of one query | one forward pass | can be exponential, or undecidable in first-order logic |
| Inspection | opaque weights | every step can be checked |
Almost every design combines them in one of three ways:
- Learning guides search. A search over proofs, programs or moves keeps its rules, so every solution it returns is valid; a network only decides which branch of the search tree to try first. AlphaZero, which runs Monte Carlo tree search over the rules of the game with policy and value networks, is the template.
- Logic shapes learning. Rules become differentiable functions of a network's outputs, used as a loss or as a layer, so gradient descent pushes the network toward predictions that satisfy them.
- Translate, then reason. A network maps raw input such as an image or a sentence to symbols, and a symbolic engine computes or checks the answer. A large language model that writes code for an interpreter, or a proof for a proof checker, is the modern example.
Kautz (2020) refined this into a six-way taxonomy, but these three already explain where each system's guarantees come from.
Think first In pattern 1, suppose the learned policy is badly wrong and ranks the correct branch last. If the underlying search is sound and complete, what does that cost?
Only time. The search still returns a correct solution whenever one exists within its budget, and whatever it returns has passed the symbolic rules. The network affects efficiency, not correctness. Patterns 2 and 3 give up part of this guarantee: a relaxed rule is satisfied only approximately, and a translation can be wrong before any sound reasoning starts.
Program synthesis as search
In programming by example, a user supplies input–output pairs, and the system must find a program in a fixed domain-specific language (DSL) that maps every input to its output. FlashFill (Gulwani, 2011), which completes a spreadsheet column from one or two examples, turned the idea into a feature of Excel 2013. Take a toy DSL of arithmetic expressions in one input :
Depth 0 allows only the 2 leaves. Depth at most 1 allows expressions: a leaf, or an operator applied to two leaves. How many expressions have depth at most 2?
Show the answer
202
An expression of depth at most 2 is a leaf (2 ways) or one of 2 operators applied to two expressions of depth at most 1 ( ways): . Each extra level roughly squares the count.
Let count the expressions of depth at most . A deeper expression is a leaf, or an operator applied to two shallower ones:
So , , and . Dropping the gives a clean lower bound, since :
The count is doubly exponential in depth: every extra level squares it. Real DSLs have dozens of operators and constants, so blind enumeration of syntax stalls after a handful of levels.
Synthesizers survive by pruning. Two programs that produce the same outputs on every example input are interchangeable inside any larger program, as far as the examples can tell. Bottom-up enumeration therefore keeps one program per behavior:
function BOTTOM-UP(grammar G, examples (x1,y1), …, (xm,ym)) returns a program
bank ← empty map from output vectors to programs
for size = 1, 2, 3, … do
for each program P of this size, built by one rule of G
from smaller programs already in bank do
v ← (P(x1), …, P(xm)) // P's behavior on the examples
if v = (y1, …, ym) then return P // consistent with every example
if v is not yet a key of bank then
bank[v] ← P // keep the first, smallest onePrograms with equal output vectors are observationally equivalent on the examples, so the bank grows with the number of distinct behaviors, not of programs: , and are stored once. The first consistent program found is also a smallest one, an Occam bias that the Deep Layer turns into a generalization bound.
FlashFill goes further. For string transformations it represents every program consistent with an example as a directed acyclic graph whose edges carry sets of substring expressions, a version space: exponentially many programs in polynomial space. Intersecting the graphs of several examples keeps the programs consistent with all of them, and a ranking function, hand-tuned at first and later learned, picks the most plausible. One example rarely pins down the intended program, so much of the intelligence sits in the ranking.
Learned guidance
A model makes search cheaper by ranking candidates. Suppose a network reads the examples and outputs a probability distribution over programs, and the synthesizer tries programs in order of decreasing . How long until it reaches the intended program ?
In bits, : the cost of search is the target's description length under the model. A model that raises from to cuts the worst case from about candidates to about , and every candidate is still checked against the examples.
DeepCoder (Balog et al., 2017) predicted from the examples which DSL functions a program uses and ordered its search accordingly, which made it about an order of magnitude faster than unguided search. DreamCoder (Ellis et al., 2021) also changes the language: after solving a batch of tasks, it refactors the solutions into reusable library functions, so later solutions become shorter and therefore cheaper to find.
Think first A library function adds one more choice at every node of the search. Why can adding it still make search much faster?
Search cost scales like for choices per node and programs of choices. Suppose a library function replaces a recurring 8-choice subprogram, shortening a 20-choice program by 7. With , one use turns candidates into : the extra choice costs a factor of per position, while each position removed saves a factor of 10.
Logic as a differentiable loss
To train a network with a rule, the rule needs a gradient. Real-valued logics replace true and false by degrees of truth in , and the connectives by functions that agree with Boolean logic on . Conjunction becomes a t-norm : commutative, associative, monotone, with . Three are standard:
| Logic | |||
|---|---|---|---|
| Product | (Reichenbach) | ||
| Gödel | (Kleene–Dienes) | ||
| Łukasiewicz |
Take the rule , with network outputs and . Under the product logic its truth value, and a loss to minimize, are
The partial derivatives say how each output can raise the truth value:
For a raven () the gradient pushes up: modus ponens. But most objects are neither ravens nor black, and for them the gradient pushes only on :
Summed over a dataset, most of the signal says "this is not a raven", which is modus tollens: the rule gets satisfied by denying antecedents rather than by learning colors. Van Krieken, Acar and van Harmelen (2022) found such imbalances across the common operators, so choosing the logic is a modeling decision with consequences.
Under the product logic, a batch contains many objects with and . On these objects, which output does the rule mainly push?
- , upward, since
- , downward, since
- Neither: the rule is satisfied, so the gradient is zero
- Both equally, by the symmetry of the implication
Show the answer
B. , downward, since
, while is eighteen times smaller. On these objects the rule mostly teaches "these are not ravens", not "ravens are black".
A second route treats the outputs as probabilities of independent Boolean variables and asks how likely the constraint is to hold: a weighted model count, which sums the probability of every assignment that satisfies the constraint. For "exactly one of three classes", the semantic loss (Xu et al., 2018) is
DeepProbLog (Manhaeve et al., 2018) applies the same idea to whole logic programs. A network classifies each of two handwritten digits, a short program says that their sum is the sum of the digits, and training sees only the sums: . The gradient of flows through the program into the digit classifier, which learns to read digits without ever seeing a digit label.
Generate, then verify
Language models invert the division of labor: the network generates candidates freely, and a symbolic tool checks them. Checking is often far easier than generating. A proof checker, a unit-test suite or a check that an assignment satisfies a formula runs quickly even when finding the object is hard. One popular pipeline uses the model only as a translator: it turns a word problem into formal sentences, and a solver decides the question. Try the solver's half on a knights-and-knaves puzzle, where knights always tell the truth and knaves always lie.
Alice says: "Bob is a knave." Bob says: "Alice and I are both knights." Let the atom mean "Alice is a knight", and likewise for . A speaker is a knight exactly when their statement is true, so each statement becomes a biconditional: and .
When a checker can test the final answer, more samples buy more reliability. If each sample is independently correct with probability and a perfect verifier recognizes a correct one, the chance that at least one of samples passes is
A model solves a programming problem in 10% of its samples, and the problem's unit tests recognize a correct solution perfectly. How many independent samples give a 95% chance that at least one passes?
Show the answer
29
You need , so : 29 samples. Without the tests, those samples would be far less useful, because nothing would tell you which one to keep.
Without a verifier, the usual substitute is a vote. Chain-of-thought prompting (Wei et al., 2022) has the model write intermediate steps before its answer, and self-consistency (Wang et al., 2023) samples several chains at a temperature above zero and returns the most frequent final answer. Voting helps exactly when the correct answer is the model's most likely one. In the simplest case of one wrong alternative, if each chain is right with probability , a majority of 11 chains is right 75% of the time and a majority of 41 chains 90%. At the same votes make things worse: 37% and 26%.
The written steps also buy computation. A transformer does a bounded amount of work per token, so writing intermediate results lets it carry out serial computations that it cannot fit into a single pass. The Deep Layer makes this precise.
Limits, and where to go deeper
Every guarantee above covers the symbolic step and nothing else. The open problems sit at the seams:
- Translation errors. In translate-then-reason pipelines, mistakes in reading the problem happen before any sound reasoning starts, and nothing downstream catches them.
- Unfaithful reasoning. A chain of thought is text written before an answer, not necessarily the computation that produced it. Turpin et al. (2023) biased few-shot prompts toward one answer option; models followed the bias and wrote explanations that almost never mentioned it.
- Compositional generalization. Networks that do well on inputs like their training data can fail on new combinations of familiar parts, such as longer multiplications or longer chains of rules (the SCAN experiments in Symbols vs. Connections are the classic case).
- Reasoning shortcuts. A network trained only through a rule can satisfy the rule with the wrong concepts. If a label is the XOR of two concepts, negating both concepts fits every label equally well.
- Scarce verifiers. Mathematics in a proof assistant and code with tests have checkers. Most questions people ask do not, and there a fluent answer can be a hallucination.
Key takeaways
- Neurosymbolic systems combine learning and logic in three main ways: learned guidance inside symbolic search, logic relaxed into differentiable losses, and generation followed by symbolic checking or reasoning.
- Program spaces grow doubly exponentially with depth. Observational equivalence and version spaces prune them, and best-first enumeration under a model reaches within candidates.
- T-norms make rules differentiable, but their gradients carry biases; weighted model counts give exact probabilistic losses that are #P-hard in general.
- A sound verifier turns sampling into reliability, . Voting without one only amplifies the model's most likely answer.
- Guarantees cover only the symbolic step: translation errors, unfaithful chains of thought and reasoning shortcuts live outside it.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Bottom-up enumeration discards a newly built program when…
- its outputs on the example inputs equal those of a program already in the bank
- it is longer than the programs found so far
- it gets at least one example wrong
- a neural network assigns it a low probability
Show the answer
A. its outputs on the example inputs equal those of a program already in the bank
Programs with the same outputs on every example input behave identically inside any larger program, as far as the examples can tell, so one representative suffices. Programs that fail the examples are kept as building blocks.
A synthesizer tries programs in decreasing order of a model's probability , and the intended program has . What is guaranteed?
- is found within 20 candidates
- is found first
- Nothing: it depends on the other programs' probabilities
- is found within about a million candidates
Show the answer
D. is found within about a million candidates
At most programs can have probability at least , so is among the first million, whatever the rest of looks like.
Which statement about the product, Gödel and Łukasiewicz logics is true?
- They give the same truth values for all inputs in
- They agree with Boolean logic when every input is 0 or 1, and differ in between
- Only the product logic has usable gradients
- Łukasiewicz conjunction is
Show the answer
B. They agree with Boolean logic when every input is 0 or 1, and differ in between
All three extend the Boolean connectives. In between they differ, and so do their gradients: passes gradient to one argument only, and has zero gradient whenever .
A language model translates a puzzle into logic, and a sound and complete solver answers the question. The final answer is wrong for the puzzle. Where must the error lie?
- In the solver, since its output was wrong
- Nowhere: a sound solver guarantees a correct final answer
- In the translation: the solver answered correctly for the formulas it was given
- In the solver's handling of tautologies
Show the answer
C. In the translation: the solver answered correctly for the formulas it was given
A sound and complete solver answers correctly about its input formulas. If its answer is wrong for the puzzle, the formulas do not say what the puzzle says.
Self-consistency returns the most frequent answer among sampled chains of thought. For one question, each chain is right with probability 0.45 and otherwise gives the same wrong answer. What happens as you sample more chains?
- Accuracy rises toward 100%
- Accuracy stays at 45%
- Accuracy approaches 50%
- Accuracy falls toward 0%
Show the answer
D. Accuracy falls toward 0%
The majority converges to the likelier answer, here the wrong one: a majority of 41 chains is right only about 26% of the time, and the accuracy tends to 0 as more chains are sampled. Voting sharpens a model's beliefs; it cannot correct them.
Go deeper
- Program Synthesis · Learning programs from examples and specifications.
- Differentiable Reasoning · Soft logic, neural theorem provers and their limits.
- Reasoning in Language Models · Chain of thought, search over thoughts and verification.
Further reading
- S. Gulwani, "Automating string processing in spreadsheets using input-output examples," POPL (2011).
- R. Manhaeve, S. Dumančić, A. Kimmig, T. Demeester & L. De Raedt, "DeepProbLog: Neural probabilistic logic programming," NeurIPS (2018).
- J. Wei et al., "Chain-of-thought prompting elicits reasoning in large language models," NeurIPS (2022).
- T. H. Trinh, Y. Wu, Q. V. Le, H. He & T. Luong, "Solving olympiad geometry without human demonstrations," Nature 625, 476–482 (2024).