SymBa: Symbolic Backward Chaining for Structured Natural Language Reasoning

Jinu Lee, Wonseok HwangNAACL 2025 · DOI

Abstract

SymBa is a neuro-symbolic reasoning framework that integrates a classic symbolic solver (SLD Resolution) with Large Language Models (LLMs) to perform backward chaining. By letting a rigorous symbolic engine control the reasoning process while using the LLM only for translation and search, SymBa achieves state-of-the-art accuracy and massive efficiency gains (up to 22x speedup) over previous "incomplete" LLM-based reasoning methods.

Introduction

While Large Language Models (LLMs) demonstrate impressive text generation capabilities, their "Chain-of-Thought" (CoT) reasoning often suffers from logical fallacies or factual inaccuracies. To mitigate this, researchers have explored "structured reasoning," where models generate formal proof trees. However, current state-of-the-art methods like Least-to-most prompting and LAMBADA are essentially "incomplete" versions of classic logic algorithms. They frequently lack critical features such as backtracking—the ability to explore alternative paths when one fails—and binding propagation—the ability to pass specific variables across proof steps. This incompleteness makes them brittle for complex relational or arithmetic tasks.

Methodology: Symbolic Backward Chaining

The authors propose SymBa (Symbolic Backward Chaining), which structures reasoning as a coroutine between a symbolic solver and an LLM.

The four core steps of SymBa's symbolic backward chaining: Search, Decompose, Binding Propagation, and Backtracking.

The system operates through two primary components:

  1. The Symbolic Solver: SymBa utilizes a classic SLD (Selective Linear Definite) Resolution solver, similar to the engine powering Prolog. This solver manages the search tree, handles variable bindings, and executes backtracking.
  2. The LLM as Translator and Searcher: The LLM is invoked only when the solver requires external information. It performs Fact/Rule Search (locating relevant natural language sentences) and Fact/Rule Translation (converting sentences into symbolic logic, e.g., "Alan is young" to is(alan, young)).

Before any LLM-generated rule enters the solver's database, it undergoes Symbolic Validation to ensure syntactic correctness and unification with the current goal, preventing hallucinations from derailing the process.

Evaluation and Results

SymBa was evaluated across seven benchmarks involving deductive, relational (CLUTRR), and arithmetic (GSM8k, MAWPS) reasoning.

Comparison of SymBa's complete SLD resolution against incomplete methods like Least-to-most prompting and LAMBADA.

Key Performance Metrics

  • Superior Accuracy: SymBa consistently outperformed baselines. On the Birds-Electricity dataset with GPT-4, SymBa reached 94.4% accuracy, surpassing Least-to-most (88.2%) and LAMBADA (83.4%).
  • Arithmetic Dominance: On GSM8k, SymBa achieved 63.8% accuracy. In contrast, LAMBADA scored 0% because it lacks the binding propagation necessary to handle numeric variables.
  • Efficiency: By specializing the LLM's role to short translation tasks, SymBa is 9x more cost-effective and 22x faster than LAMBADA.

Discussion: Why Completeness Matters

The success of SymBa highlights that LLM reasoning failures are often algorithmic rather than purely linguistic. By employing a complete SLD solver, SymBa ensures that if a proof exists within the provided text, the system will find it. Previous methods often fail by getting trapped in a single unsuccessful branch of a search tree. Furthermore, native handling of binding propagation allows SymBa to solve arithmetic problems that other backward-chaining methods cannot "carry" values through.

Limitations and Future Work

Despite its strengths, SymBa relies on the LLM for initial translation; errors at this stage cannot be corrected by the symbolic solver. It also struggles with high-order logic ("meta-predicates") and operates under a closed-world assumption, which may conflict with open-ended human common sense. Future research may explore hybrid forward-and-backward chaining to better handle fact-intensive knowledge-base tasks.

Summary updated

BibTeX
@inproceedings{lee2025symba,
  author = {Jinu Lee and Wonseok Hwang},
  title = {{SymBa: Symbolic Backward Chaining for Structured Natural Language Reasoning}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2025},
  doi = {10.18653/v1/2025.naacl-long.124},
}
Figure