NELLIE: A Neuro-Symbolic Inference Engine for Grounded, Compositional, and Explainable Reasoning

Nathaniel Weir, Peter Clark, Benjamin Van Durme

TL;DR

NELLIE is a neuro-symbolic inference engine that combines the logical rigor of Prolog-style backward chaining with the linguistic flexibility of Large Language Models (LLMs). By decomposing questions into proof trees grounded in a verified text corpus, NELLIE provides human-interpretable answers that are "faithful by design," significantly reducing the hallucinations common in standard LLMs.

What Problem Does This Paper Address?

While modern LLMs are impressive at question answering, they remain "black boxes." Their reasoning is often opaque, and they are prone to hallucinations—generating plausible-sounding but factually incorrect information. Current explainability methods like Chain-of-Thought (CoT) generate rationales from the model's internal weights, but these rationales aren't necessarily grounded in external, authoritative facts.

Conversely, traditional symbolic "expert systems" are highly transparent and logical but are notoriously brittle and expensive to build because they require humans to manually write hundreds of formal rules. The authors aim to bridge this gap: creating a system that is as logical as a symbolic reasoner but as linguistically capable as a neural model, all while ensuring every step of reasoning is backed by a specific sentence in a trusted knowledge base.

Methods

NELLIE operates as a neuro-symbolic backward chaining engine. It starts with a hypothesis (a potential answer to a question) and works backward to find a proof.

  1. Question Conversion: It first converts a multiple-choice question and its options into declarative hypotheses using a QA-to-Declarative model.
  2. Dynamic Rule Generation (DRG): Instead of using handcrafted rules, NELLIE uses a T5-3B model to dynamically generate "if-then" rules. For example, to prove "Chlorophyll helps plants produce sugar," the DRG might suggest two sub-hypotheses: "Chlorophyll causes plants to absorb light" AND "Plants use light to produce carbohydrates."
  3. Weak Unification via NLI: In classical logic, symbols must match exactly. NELLIE uses Natural Language Inference (NLI) to perform "weak unification," checking if a retrieved fact from the corpus entails a hypothesis, even if the wording is different.
  4. Search Guidance: To navigate the massive search space of natural language, the authors introduced two steering mechanisms:
  5. Template-Conditioned Generation (TCG): Uses structural templates (e.g., "X is a kind of Y") to bias the model toward generating rules that look like facts in the corpus.
  6. Retrieval-Conditioned Generation (RCG): Retrieves a relevant fact first and then forces the model to generate a rule that incorporates that specific fact.
  7. Proof Tree Construction: The system recursively attempts to prove sub-hypotheses until it reaches "leaves"—sentences that exist directly in the provided text corpus.
Figure 3: Proposed system framework. An off-the-shelf theorem prover searches for proofs of query PROVE(h), where symbol h is an NL hypothesis translated from a QA pair. The prover uses a set of meta-axioms invoking neural retrieval, entailment, and generation predicates to dynamically instantiate inference rules that use the NL factbase.

Datasets

The researchers evaluated NELLIE primarily in the science domain using:

  • WorldTree: A corpus of ~9,000 science facts organized into semi-structured tables.
  • EntailmentBank: A dataset of multi-step entailment trees for elementary science questions.
  • OpenBookQA (OBQA): A dataset requiring multi-hop reasoning over science facts and common knowledge.
  • eQASC and SciTail: Used for training the underlying NLI filters and rule generators.

Key Insights and Ideas

  • Faithfulness by Constraint: By requiring the proof search to terminate in a specific corpus of facts, NELLIE is structurally prevented from hallucinating facts that don't exist in its "textual library."
  • Logical Directionality: Unlike many graph-based QA systems that just link related entities, NELLIE produces a directed proof where each step logically follows from the ones below it.
  • Scalability via Text: A key advantage over old expert systems is that NELLIE can be "taught" new domains simply by giving it a new text corpus; it doesn't require a knowledge engineer to write new code or rules.
  • The Search Challenge: Grounding is hard. NELLIE often has to consider hundreds or thousands of potential proof paths to find the one that is fully supported by the text, whereas non-grounded models only look at a few.
Figure 2: Comparison of approaches to neural XQA. Each approach leads to NL graphs in support of a query. Our proposal is to pro- duce logically directed explanations containing model-generated intermediate steps while grounding a tree in verified facts without relying on handwritten horn clauses.

Key Results

  • Performance: NELLIE (3B parameters) achieved 71.4% accuracy on EntailmentBank QA, outperforming a similar-sized non-grounded reasoner (Entailer-3B) by over 22 points.
  • Competitive with Giants: It performed within 2 points of Entailer-11B, a model nearly four times its size that doesn't face the strict constraint of grounding every proof step in a corpus.
  • Ablation Studies: The guidance mechanisms are vital. Removing Retrieval-Conditioned Generation (RCG) caused accuracy to drop by 3-4 points, proving that "looking at the facts" before reasoning is essential for grounded search.
Figure 6: Effect of ablating one or both of rule-conditioned (RCG) and template-conditioned generation (TCG).

Limitations and Future Work

  • Computational Cost: The backward chaining search is expensive, requiring many LLM calls to explore potential proof trees.
  • Semantic Drift: In long proofs, the meaning of a statement can shift slightly between steps (e.g., confusing "heat transfer" with "temperature decrease"), leading to logical failures.
  • Logical Fallacies: The model occasionally falls for the "fallacy of the undistributed middle" (e.g., assuming that because penguins are birds and birds fly, penguins must fly).
  • Future Directions: The authors suggest improving the "self-ask" filters to catch these logical errors earlier and optimizing the search algorithm to handle even larger, more diverse knowledge bases.

Summary updated

Abstract

Our goal is a modern approach to answering questions via systematic reasoning where answers are supported by human interpretable proof trees grounded in an NL corpus of authoritative facts. Such a system would help alleviate the challenges of interpretability and hallucination with modern LMs, and the lack of grounding of current explanation methods (e.g., Chain-of-Thought). This paper proposes a new take on Prolog-based inference engines, where we replace handcrafted rules with a combination of neural language modeling, guided generation, and semiparametric dense retrieval. Our implementation, NELLIE, is the first system to demonstrate fully interpretable, end-to-end grounded QA as entailment tree proof search, going beyond earlier work explaining known-to-be-true facts from text. In experiments, NELLIE outperforms a similar-sized state-of-the-art reasoner [Tafjord et al., 2022] while producing knowledge-grounded explanations. We also find NELLIE can exploit both semi-structured and NL text corpora to guide reasoning. Together these suggest a new way to jointly reap the benefits of both modern neural methods and traditional symbolic reasoning.
BibTeX
@inproceedings{weir2024nellie,
  author = {Nathaniel Weir and Peter Clark and Benjamin Van Durme},
  title = {{NELLIE: A Neuro-Symbolic Inference Engine for Grounded, Compositional, and Explainable Reasoning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=782ySPQoqw},
}
Figure