💬 NLP

Sound and Complete Neurosymbolic Reasoning with LLM-Grounded Interpretations

This paper presents a neurosymbolic reasoning framework that integrates Large Language Models into the interpretation function of a paraconsistent logic, enabling sound and complete formal reasoning that leverages LLM knowledge while effectively localizing contradictions to prevent logical explosion and improve factuality benchmarks.

Original authors: Bradley P. Allen, Prateek Chhikara, Thomas Macaulay Ferguson, Filip Ilievski, Paul Groth

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bradley P. Allen, Prateek Chhikara, Thomas Macaulay Ferguson, Filip Ilievski, Paul Groth

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: Smart but Unreliable

Imagine you have a brilliant, encyclopedic assistant (a Large Language Model, or LLM) who knows almost everything. You ask them a question, and they give you a confident answer. But sometimes, they get it wrong. Sometimes, they give you two answers that contradict each other (e.g., "This drug is safe" and "This drug is dangerous").

In the world of traditional logic, if you have a contradiction, the whole system crashes. It's like a computer program that says "If A is true and A is false, then the sky is green and the moon is made of cheese." This is called logical explosion, and it makes the system useless.

The authors of this paper asked: How can we use this super-smart but sometimes contradictory assistant to help us reason about facts without the whole system crashing?

The Solution: A "Belnap Computer" with a Twist

The authors built a new kind of reasoning machine they call a Belnap computer. Think of it as a very strict judge who doesn't just ask "Is this true or false?" but asks two separate questions:

Can you prove this is true?
Can you prove this is false?

Instead of forcing a single "Yes" or "No," the system accepts four possible states for any piece of information:

True: You can prove it, but you can't prove it's false.
False: You can prove it's false, but you can't prove it's true.
Glut (Contradiction): You can prove it's true AND you can prove it's false. (The assistant is confused or the facts conflict).
Gap (Ignorance): You can't prove it's true AND you can't prove it's false. (The assistant doesn't know).

How It Works: The "Fact-Checker" Duo

The paper introduces a method called Bilateral Factuality Evaluation. Imagine you have a team of two fact-checkers working on a single statement:

Fact-Checker A tries to find evidence to verify the claim.
Fact-Checker B tries to find evidence to refute (disprove) the claim.

They don't just say "True" or "False." They report back with a scorecard:

If A says "Verified" and B says "Cannot Refute," the claim is True.
If A says "Cannot Verify" and B says "Refuted," the claim is False.
If both say "Verified" and "Refuted," we have a Glut (a contradiction).
If both say "Cannot Verify" and "Cannot Refute," we have a Gap (we don't know).

The paper shows that by using this "two-sided" approach, the system becomes much better at spotting when the AI is confused or when the facts are messy, rather than just guessing.

The Magic Trick: Keeping the Logic Safe

The most impressive part of the paper is how they connect this messy AI to strict math. Usually, if you plug a "noisy" AI into a strict logic system, the math breaks.

The authors proved mathematically that they can plug the AI directly into the "definition of truth" for their logic system without breaking the rules.

The Analogy: Imagine a strict traffic light system (the logic). Usually, the light must be either Red or Green. The authors showed they can install a "smart camera" (the AI) that sometimes says "It's Red AND Green" or "I don't know."
The Result: Even though the camera is confused, the traffic light system doesn't crash. It simply acknowledges the confusion, keeps the lights working for the cars that do have clear signals, and flags the confusing intersection for a human to look at later. The system remains satisfiable (it keeps working) even with contradictions.

Real-World Test: The Medication Safety Lab

To prove this works, the authors built a prototype system to check a database of medication rules.

They fed the system rules like "All benzodiazepines are non-addictive" (which is medically false).
The system used the AI to check these rules against its internal knowledge.
The Outcome: The AI flagged the false rules. It found 92 contradictions (gluts). For example, it knew that "Opioids are non-addictive" was a lie because it could both verify the rule (from the database) and refute it (from its medical knowledge).
Crucially: The system didn't crash. It didn't say "Everything is true now." Instead, it said, "I found 92 specific errors, but the rest of the system is still working correctly."

The Trade-off: Quality vs. Quantity

The paper found a trade-off. When the system uses this "two-sided" check:

It gets better at being right (higher accuracy).
It answers fewer questions (lower coverage).

Why? Because if the AI is confused or doesn't know, the system politely says, "I'm not sure, I'll skip this one," rather than guessing. It's like a doctor who refuses to diagnose a patient when symptoms are unclear, rather than guessing and potentially harming the patient.

Summary

This paper presents a way to use powerful AI assistants for serious reasoning tasks without letting their mistakes break the whole system. By asking the AI to check for both proof and disproof, and by using a special type of logic that tolerates contradictions, they built a system that can:

Spot when the AI is confused.
Identify specific errors in knowledge bases (like bad medical rules).
Keep working safely even when contradictions exist, rather than crashing.

It's a bridge between the messy, human-like knowledge of AI and the strict, reliable world of formal logic.

Technical Summary: Sound and Complete Neurosymbolic Reasoning with LLM-Grounded Interpretations

Problem Statement

Large Language Models (LLMs) possess vast parametric knowledge but suffer from inherent inconsistencies and incompleteness, making them unreliable as standalone knowledge bases for formal reasoning. Traditional approaches to neurosymbolic reasoning—such as prompting LLMs to perform logical reasoning, using them to generate symbolic inputs for external solvers, or fine-tuning them on proofs—fail to provide formal guarantees regarding the soundness and completeness of the reasoning process when the LLM's knowledge is contradictory. Furthermore, standard factuality evaluation methods typically yield a single truth value, obscuring the LLM's epistemic state (e.g., whether it is uncertain or genuinely conflicted). The core challenge is how to integrate an LLM's broad-coverage knowledge into a formal reasoning system while preserving the logic's theoretical properties (soundness and completeness) and effectively managing the inconsistencies the LLM produces.

Methodology

The authors propose a framework that integrates an LLM directly into the interpretation function of a paraconsistent logic, specifically Analytic Containment (AC), a bilateral logic capable of handling inconsistent information without logical explosion.

1. Bilateral Factuality Evaluation

Instead of asking an LLM to assign a single truth value (True/False), the system employs a bilateral evaluation approach. An LLM judge is prompted to independently assess two conditions for an atomic formula $\phi$ :

Verification ( $P^+$ ): Can the LLM verify $\phi$ ?
Refutation ( $P^-$ ): Can the LLM refute $\phi$ ?

The outputs are mapped to weak Kleene truth values ( $t$ =true, $f$ =false, $e$ =undefined/unknown). These are paired to form a generalized truth value $\langle u, v \rangle \in V_3 \times V_3$ . This results in four primary states:

$\langle t, f \rangle$ : Verified (True).
$\langle f, t \rangle$ : Refuted (False).
$\langle t, t \rangle$ : Glut (Both verified and refuted; inconsistency).
$\langle f, f \rangle$ : Gap (Neither verified nor refuted; uncertainty/ignorance).

To ensure the stability required for formal reasoning, a caching mechanism ( $\zeta_c$ ) is used, storing the valuation of atomic formulas immutably once computed.

2. LLM-Grounded Interpretations

The paper defines an LLM-grounded interpretation ( $I$ ) where the interpretation of atomic formulas is determined by the cached bilateral evaluation function $\zeta_c$ .

Theoretical Integration: The authors prove that for every LLM-grounded interpretation, there exists an equivalent standard interpretation, and vice versa.
Preservation of Properties: They demonstrate that the soundness and completeness of the analytic tableau system for AC (specifically $AC^{rQ}$ ) are preserved even when the interpretation is grounded in an LLM. This means the reasoner can formally derive conclusions with the same guarantees as a standard logic, despite the LLM's potential for inconsistency.

3. Implementation: A Belnap Computer

The authors implemented a proof-of-concept Belnap computer (a reasoner designed to handle inconsistent information) in Python.

Architecture: It combines forward-chaining inference (deriving new facts from rules) with tableau-based satisfiability checking.
LLM Evaluation Rule: During tableau construction, an llm-eval rule queries the LLM judge for the bilateral truth value of atomic formulas.
Glut Handling: When a glut is detected (e.g., the system infers $P(a)$ but the LLM refutes it), the tableau does not close (explode). Instead, it maintains both the assertion and its refutation, localizing the contradiction.

Key Contributions

Bilateral Factuality Evaluation: A novel method that surfaces the LLM's epistemic state (consistent, inconsistent, or uncertain) rather than forcing a binary decision, providing more actionable diagnostics than unilateral evaluation.
LLM-Grounded Interpretations: A theoretical framework that integrates LLMs directly into the formal semantics of a paraconsistent logic, preserving the soundness and completeness of the underlying reasoning system.
Empirical Validation: Demonstration that bilateral evaluation improves macro-F1 scores over unilateral baselines (by ~6 percentage points) on factuality benchmarks (GPQA and SimpleQA), albeit with reduced coverage due to abstention on uncertain cases.
Practical System: A working implementation of a Belnap computer that successfully detects medically significant errors (gluts) in a knowledge base while maintaining overall satisfiability.

Experimental Results

The authors evaluated the approach using datasets derived from GPQA and SimpleQA benchmarks with various LLMs (flagship and distilled models).

Accuracy vs. Coverage: Bilateral evaluation achieved a higher macro-F1 score (approx. 0.699 for flagship models on GPQA) compared to unilateral baselines (0.633), but with lower coverage (0.589 vs. 1.000). The system abstains on inconsistent ( $\langle t, t \rangle$ ) or uncertain ( $\langle f, f \rangle$ ) cases, leading to higher reliability on the cases where it does provide an answer.
Epistemic States: The experiments revealed that LLMs frequently produce gluts (inconsistencies) rather than gaps. For example, on the SimpleQA dataset, GPT models showed a high tendency toward contradiction (glut rates ~59%), while Claude models were more cautious (higher gap rates).
Medication Safety Use Case: The system was applied to a knowledge base of 228 asserted and 712 inferred statements regarding medication safety.
- It detected 92 gluts corresponding to medically significant errors (e.g., inferring opioids are non-addictive or beta-blockers are safe for asthma patients).
- Despite these 92 contradictions, the system remained satisfiable, successfully localizing the errors without causing logical explosion.
- Computational analysis showed that LLM latency is the dominant bottleneck, but the approach is scalable to medium-sized knowledge bases (100k+ statements) with standard optimizations like parallelization and caching.

Significance and Claims

The paper claims to offer a theoretical framework with a practical implementation for neurosymbolic reasoning that leverages an LLM's knowledge while preserving the underlying logic's soundness and completeness.

Paradigm Shift: Unlike prior work that attempts to make LLMs reason using logic, this approach makes the logic reason using the LLM as an interpretation oracle.
Robustness: The system is designed for real-world scenarios where knowledge sources are inherently inconsistent. It treats contradictions not as fatal errors requiring repair, but as localized epistemic states (gluts) that can be identified and managed.
Actionable Diagnostics: By distinguishing between "conflicted" (glut) and "ignorant" (gap) states, the system provides downstream applications with specific information on why a conclusion is uncertain, enabling more conservative and safe decision-making (e.g., in medical contexts).
Scalability: The authors argue that while LLM API latency is currently the primary cost, the logical overhead is minimal, and the system is tractable for production-scale knowledge bases using existing optimization techniques from description logic reasoners.