SymBa: Symbolic Backward Chaining for Structured Natural Language Reasoning
This addresses the need for more reliable and explainable reasoning in AI systems, though it is an incremental advance over existing methods.
The paper tackled the problem of incomplete LLM-based backward chaining for structured natural language reasoning by proposing SymBa, which integrates a symbolic solver with an LLM, resulting in significant improvements across seven reasoning benchmarks.
To improve the performance and explainability of LLM-based natural language reasoning, structured reasoning can be applied to generate explicitly structured proofs. Among different methods for structured reasoning, we specifically focus on backward chaining, where the proof goal is recursively decomposed to subgoals by searching and applying rules. We argue that current LLM-based backward chaining systems (e.g. Least-to-most prompting and LAMBADA) are incomplete, as they omit crucial algorithmic components identified from the classic backward chaining algorithm in computational logic (SLD Resolution). To this end, we propose a novel backward chaining system, SymBa (Symbolic Backward Chaining), which integrates a symbolic solver and an LLM. In SymBa, the solver controls the proof process, and the LLM is only called when the solver requires new information to complete the proof. Empowered by completeness, SymBa achieves a significant improvement in seven deductive, relational, and arithmetic reasoning benchmarks compared to the baselines.