Simple Algorithm
Artificial Intelligence · Hidden Layer · 22 min

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 1/q(P∗)1/q(P^*).
  • 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@kk 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.

PropertyLearned modelsSymbolic reasoners
Where knowledge comes fromfitted to datawritten by people, or derived from written facts
What is guaranteedaverage accuracy on the training distributionsoundness (sometimes completeness) relative to the premises
Inputs unlike the training datacan fail silentlyno change, if the premises still hold
Noisy or perceptual inputhandled naturallyneeds clean symbols
Cost of one queryone forward passcan be exponential, or undecidable in first-order logic
Inspectionopaque weightsevery step can be checked
Each column's strengths are the other's weaknesses.

Almost every design combines them in one of three ways:

  1. 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.
  2. 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.
  3. 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 xx:

E  →  x  ∣  1  ∣  E+E  ∣  E×EE\;\to\;x\;\mid\;1\;\mid\;E+E\;\mid\;E\times E
Two leaves and two binary operators. The examples (x,y)=(1,2),(2,5),(3,10)(x,y)=(1,2),(2,5),(3,10) are fit by x×x+1x\times x+1.
Predict before you look

Depth 0 allows only the 2 leaves. Depth at most 1 allows 2+2×2×2=102+2\times2\times2=10 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 (10×1010\times10 ways): 2+2⋅100=2022+2\cdot100=202. Each extra level roughly squares the count.

DerivationHow fast the program space grows
  1. N(0)=2,N(d)=2+2 N(d−1)2N(0)=2,\qquad N(d)=2+2\,N(d-1)^2

    Let N(d)N(d) count the expressions of depth at most dd. A deeper expression is a leaf, or an operator applied to two shallower ones:

  2. 2N(d) ≥ (2N(0))2d=42d⟹log⁡2N(d) ≥ 2d+1−12N(d)\ \ge\ \big(2N(0)\big)^{2^d}=4^{2^d}\qquad\Longrightarrow\qquad \log_2N(d)\ \ge\ 2^{d+1}-1

    So N(1)=10N(1)=10, N(2)=202N(2)=202, N(3)=81,610N(3)=81{,}610 and N(4)≈1.3×1010N(4)\approx1.3\times10^{10}. Dropping the +2+2 gives a clean lower bound, since 2N(d)≥(2N(d−1))22N(d)\ge\big(2N(d-1)\big)^2:

  3. N(d)=2Θ(2d)N(d)=2^{\Theta(2^d)}

    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:

text
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 one

Programs with equal output vectors are observationally equivalent on the examples, so the bank grows with the number of distinct behaviors, not of programs: x+xx+x, x×(1+1)x\times(1+1) and (1+1)×x(1+1)\times x 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 qq over programs, and the synthesizer tries programs in order of decreasing qq. How long until it reaches the intended program P∗P^*?

In bits, log⁡2(search cost)≤−log⁡2q(P∗)\log_2(\text{search cost})\le-\log_2q(P^*): the cost of search is the target's description length under the model. A model that raises q(P∗)q(P^*) from 2−402^{-40} to 2−102^{-10} cuts the worst case from about 101210^{12} candidates to about 10310^3, 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 bℓb^{\ell} for bb choices per node and programs of ℓ\ell choices. Suppose a library function replaces a recurring 8-choice subprogram, shortening a 20-choice program by 7. With b=10b=10, one use turns 102010^{20} candidates into 1113≈3×101311^{13}\approx3\times10^{13}: the extra choice costs a factor of 1.11.1 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 [0,1][0,1], and the connectives by functions that agree with Boolean logic on {0,1}\{0,1\}. Conjunction becomes a t-norm T(a,b)T(a,b): commutative, associative, monotone, with T(a,1)=aT(a,1)=a. Three are standard:

Logica∧ba\land ba∨ba\lor ba⇒ba\Rightarrow b
Productababa+b−aba+b-ab1−a+ab1-a+ab (Reichenbach)
Gödelmin⁡(a,b)\min(a,b)max⁡(a,b)\max(a,b)max⁡(1−a, b)\max(1-a,\,b) (Kleene–Dienes)
Łukasiewiczmax⁡(0, a+b−1)\max(0,\,a+b-1)min⁡(1, a+b)\min(1,\,a+b)min⁡(1, 1−a+b)\min(1,\,1-a+b)
Negation is 1−a1-a in all three, and each implication is ¬a∨b\neg a\lor b in its own logic. On inputs in {0,1}\{0,1\} every row reduces to the Boolean truth table; in between they disagree, and so do their gradients.
DerivationThe gradient of a soft rule
  1. I(a,c)=1−a+ac,L=−log⁡I(a,c)I(a,c)=1-a+ac,\qquad \loss=-\log I(a,c)

    Take the rule Raven(x)⇒Black(x)\text{Raven}(x)\Rightarrow\text{Black}(x), with network outputs a=p(raven∣x)a=p(\text{raven}\mid x) and c=p(black∣x)c=p(\text{black}\mid x). Under the product logic its truth value, and a loss to minimize, are

  2. ∂I∂c=a(make it black),∂I∂a=−(1−c)(make it less of a raven)\frac{\partial I}{\partial c}=a\quad\text{(make it black)},\qquad \frac{\partial I}{\partial a}=-(1-c)\quad\text{(make it less of a raven)}

    The partial derivatives say how each output can raise the truth value:

  3. (a,c)≈(0,0)⟹∂I∂c≈0,∂I∂a≈−1(a,c)\approx(0,0)\quad\Longrightarrow\quad \frac{\partial I}{\partial c}\approx0,\qquad \frac{\partial I}{\partial a}\approx-1

    For a raven (a≈1a\approx1) the gradient pushes cc up: modus ponens. But most objects are neither ravens nor black, and for them the gradient pushes only on aa:

  4. ∑x∣∂I∂a∣ ≫ ∑x∣∂I∂c∣when ravens are rare\sum_x\Big|\frac{\partial I}{\partial a}\Big|\ \gg\ \sum_x\Big|\frac{\partial I}{\partial c}\Big|\quad\text{when ravens are rare}

    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.

Check your understanding

Under the product logic, a batch contains many objects with a=p(raven)=0.05a=p(\text{raven})=0.05 and c=p(black)=0.1c=p(\text{black})=0.1. On these objects, which output does the rule Raven⇒Black\text{Raven}\Rightarrow\text{Black} mainly push?

  1. cc, upward, since ∂I/∂c=0.05\partial I/\partial c=0.05
  2. aa, downward, since ∂I/∂a=−0.9\partial I/\partial a=-0.9
  3. Neither: the rule is satisfied, so the gradient is zero
  4. Both equally, by the symmetry of the implication
Show the answer

B. aa, downward, since ∂I/∂a=−0.9\partial I/\partial a=-0.9

∂I/∂a=−(1−c)=−0.9\partial I/\partial a=-(1-c)=-0.9, while ∂I/∂c=a=0.05\partial I/\partial c=a=0.05 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

Ls=−log⁡(p1(1−p2)(1−p3)+(1−p1) p2(1−p3)+(1−p1)(1−p2) p3)\loss_{\mathrm{s}}=-\log\Big(p_1(1-p_2)(1-p_3)+(1-p_1)\,p_2(1-p_3)+(1-p_1)(1-p_2)\,p_3\Big)
One term per satisfying assignment. The loss is zero exactly when all the probability sits on satisfying assignments. For general constraints the sum has exponentially many terms and computing it is #P-hard, but compiling the constraint into a circuit makes many practical cases tractable.

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: P(sum=z)=∑d1+d2=zp1(d1) p2(d2)P(\text{sum}=z)=\sum_{d_1+d_2=z}p_1(d_1)\,p_2(d_2). The gradient of −log⁡P(sum=z)-\log P(\text{sum}=z) 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 Alice\text{Alice} mean "Alice is a knight", and likewise for Bob\text{Bob}. A speaker is a knight exactly when their statement is true, so each statement becomes a biconditional: Alice⇔¬Bob\text{Alice}\Leftrightarrow\neg\text{Bob} and Bob⇔(Alice∧Bob)\text{Bob}\Leftrightarrow(\text{Alice}\land\text{Bob}).

When a checker can test the final answer, more samples buy more reliability. If each sample is independently correct with probability pp and a perfect verifier recognizes a correct one, the chance that at least one of kk samples passes is

pass@k=1−(1−p)k\text{pass@}k=1-(1-p)^k
Code generation reports this metric with unit tests as the verifier (Chen et al., 2021). Here pp belongs to one problem; a benchmark averages pass@kk over its problems.
Predict before you look

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 1−0.9k≥0.951-0.9^k\ge0.95, so k≥ln⁡0.05/ln⁡0.9≈28.4k\ge\ln0.05/\ln0.9\approx28.4: 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 0.60.6, a majority of 11 chains is right 75% of the time and a majority of 41 chains 90%. At p=0.45p=0.45 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 qq reaches P∗P^* within 1/q(P∗)1/q(P^*) 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, pass@k=1−(1−p)k\text{pass@}k=1-(1-p)^k. 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.

Question 1

Bottom-up enumeration discards a newly built program when…

  1. its outputs on the example inputs equal those of a program already in the bank
  2. it is longer than the programs found so far
  3. it gets at least one example wrong
  4. 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.

Question 2

A synthesizer tries programs in decreasing order of a model's probability qq, and the intended program has q(P∗)=2−20q(P^*)=2^{-20}. What is guaranteed?

  1. P∗P^* is found within 20 candidates
  2. P∗P^* is found first
  3. Nothing: it depends on the other programs' probabilities
  4. P∗P^* is found within about a million candidates
Show the answer

D. P∗P^* is found within about a million candidates

At most 1/q(P∗)=220≈1061/q(P^*)=2^{20}\approx10^6 programs can have probability at least 2−202^{-20}, so P∗P^* is among the first million, whatever the rest of qq looks like.

Question 3

Which statement about the product, Gödel and Łukasiewicz logics is true?

  1. They give the same truth values for all inputs in [0,1][0,1]
  2. They agree with Boolean logic when every input is 0 or 1, and differ in between
  3. Only the product logic has usable gradients
  4. Łukasiewicz conjunction is abab
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: min⁡\min passes gradient to one argument only, and max⁡(0,a+b−1)\max(0,a+b-1) has zero gradient whenever a+b<1a+b<1.

Question 4

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?

  1. In the solver, since its output was wrong
  2. Nowhere: a sound solver guarantees a correct final answer
  3. In the translation: the solver answered correctly for the formulas it was given
  4. 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.

Question 5

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?

  1. Accuracy rises toward 100%
  2. Accuracy stays at 45%
  3. Accuracy approaches 50%
  4. 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

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).