Bi-Chainer: Automated Large Language Models Reasoning with Bidirectional Chaining (2024)

Abstract: Large Language Models (LLMs) have shown human-like reasoning abilities but still face challenges in solving complex logical problems. Existing unidirectional chaining methods, such as forward chaining and backward chaining, suffer from issues like low prediction accuracy and efficiency. To address these, we propose a bidirectional chaining method, Bi-Chainer, which dynamically switches to depth-first reasoning in the opposite reasoning direction when it encounters multiple branching options within the current direction. Thus, the intermediate reasoning results can be utilized as guidance to facilitate the reasoning process. We show that Bi-Chainer achieves sizable accuracy boots over unidirectional chaining frameworks on four challenging logical reasoning datasets. Moreover, Bi-Chainer enhances the accuracy of intermediate proof steps and reduces the average number of inference calls, resulting in more efficient and accurate reasoning.

## introduction automated reasoning involves deriving accurate and valid conclusions from explicitly given knowledge @xcite . logical reasoning, particularly in the context of unstructured natural language text, is essential for automated knowledge discovery and has promising implications for advancements in diverse scientific fields. recently, large language models (llms) @xcite @xcite have shown promising progress in emulating human-like reasoning abilities @xcite . however, they still face challenges when it comes to complex multi-step logical reasoning problems @xcite @xcite . recent studies have enhanced reasoning capabilities by employing a modular approach that breaks * *corresponding author down complex tasks into smaller, more manageable components. selection-inference (si) @xcite utilizes forward chaining that employs iterative selection and inference steps to draw conclusions. however, the absence of explicit guidance directly targeting the goal results in subpar and imprecise selection. on the other hand, lam-bada @xcite utilizes backward chaining to handle multi-step reasoning. it starts with the goal, recursively selects rules, and iteratively proves decomposed sub-goals. however, lambada's ranking strategy, which prioritizes shorter rules assuming higher success rates, may not always be accurate. this can result in suboptimal performance and hinder the overall efficiency of the reasoning process. this drives our exploration of the bi-directional chaining method that enables forward chaining with explicit guidance towards the goal and facilitates backward chaining using determinate facts derived from forward chaining. as illustrated in figure 1 , we present bi-chainer, a modular reasoning framework that incorporates bi-directional chaining. bi-chainer can be understood as a bidirectional depth-first search algorithm that dynamically switches to the opposite reasoning direction when it encounters multiple branching options within the current direction. consequently, the intermediate reasoning outcomes obtained from the opposite reasoning direction can be employed as guidance to enhance the ongoing reasoning process on the current side. we showcase the adaptability and effectiveness of bi-chainer on four logical reasoning datasets: proofwriter @xcite , folio @xcite , ar-lsat @xcite , and pararules @xcite . the datasets encompass a broad range of logical reasoning problems, including deductive reasoning, first-order logic reasoning, and analytical reasoning. in addition to achieving quantitative improvements over unidi-hypothesis: the tiger is green. ## related works recent advancements in large language models, such as llama @xcite , palm @xcite , and gpt-4 (ope-nai, 2023), have demonstrated surprising humanlike intelligence in the area of multi-step logical reasoning. due to its huge application potential for various applications, including problem-solving, decision-making, and critical thinking @xcite , numerous research efforts have been dedicated to improving or eliciting the reasoning ability of these language models. most of them can be classified into three categories: fully supervised finetuning: some previous methods @xcite have employed fine-tuning techniques on pre-trained language models (lms) using downstream datasets to generate rationales or step-by-step solutions, effectively performing reasoning until obtaining final answers. however, these methods heavily rely on meticulously constructed finetuning datasets that explicitly capture the reasoning process. unfortunately, such high-quality data is often difficult to access or requires substantial resources to create. moreover, this reliance on specific datasets can restrict the extension of the lm's reasoning abilities to other open-ended reasoning tasks beyond the domain of the fine-tuning dataset. prompting & in-context learning: the chain of thought (cot) and its variants @xcite are the most common approaches to release and utilize llm's reasoning capabilities. cot guides the model to generate explicit step-by-step rationale before producing the final results. the rationale engineering techniques like rational refinement/exploration/verification are complementary to cot for further eliciting the reasoning capabilities more effectively via refining demonstration rationale examples @xcite , encouraging exploring diverse reasoning ways @xcite , and verifying if the generated rationales by llms lead to correct final answers @xcite . problem decomposition methods @xcite can also help facilitate the cot reasoning when tackling complex tasks by decomposing the complex problems into relatively simpler subproblems. it should be mentioned that most previous methods are forward chaining reasoning while only a few works @xcite have noticed its drawbacks and tried conducting backward chaining reasoning. hybrid methods: some other methods propose to simultaneously enhance and elicit the reasoning capabilities of llms with training and prompting techniques, respectively, like reasoning-enhanced training and prompting @xcite and bootstrapping & self-improving @xcite . our work lies in the category of prompting & in-context learning and aims to fully release the multi-step logical reasoning ability embedded in powerful llms like gpt-4. ## methodology in this section, we introduce the bi-chainer framework, which automates logical reasoning over natural language premises using bidirectional chaining. the premises c consist of a set of facts f and rules r, where rules can be deductive, first-order logic, or analytical reasoning statements. the framework aims to prove or disprove a hypothesis h based on the given premises. the hypothesis and the premise follow the form "if p, then q", where p represents the condition and q represents the consequent. ## experimental setup we describe our baselines and datasets here, and provide further implementation details in appendix b. unless stated otherwise, all experiments are based on gpt-4 (openai, 2023). ## results we now describe the results and compare bi-chainer with the baselines in detail. ## additional results performance on open-source model. we also adopt the open-sourced llama2 7b model in greedy search decoding strategy to supplement the corresponding experiments on proofwriter and pararules datasets. individual module performance. to understand which components in bi-chainer are responsible for the failure cases, we computed the individ-ual accuracy of the six modules described in section 3. for this purpose, we randomly sampled 100 examples from the validation set of proofwriter. this sampling included 20 examples for each reasoning depth. we then manually wrote the desired outputs for each module. a module prediction is considered correct if it matches our annotations. the performance of modules in bi-chainer is shown in compare width-first search framework. tree of thoughts (tot) reasoning framework @xcite performs reasoning and evaluation on each intermediate result in a tree-searching manner. thus, compared to our depth-first bi-directional searching framework, tot is a width-first searching framework, resulting in a high number of inference calls. the result comparison between tot and bi-chainer is shown in the results demonstrate that tot surpasses si but trails behind lambada in terms of performance, and falls even further behind bi-chainer. this can be attributed to tot's focus on solving general complex reasoning tasks, rather than being specifically tailored for goal-oriented tasks like logical reason-ing. besides, tot's reasoning process, which involves tree-searching for each intermediate result, leads to a significant number of inference calls. ## case study we demonstrate a case study to understand the performance of the bi-chainer method compared to lambada. we give a high-level overview and abbreviated examples here, leaving full detailed examples in appendix a. lambada experienced premise confusion, it fails to accurately determine the appropriate rule for the subsequent inference step when multiple rules unify with the consequent of the goal statement. as a result of choosing the wrong rule, the model was unable to validate the premise condition, resulting in a wrong conclusion. hypothesis: the cow chases the cow. step 1: rule 2: if someone is rough and the tiger sees the bear then they chase the cow. rule 3: if someone likes the tiger then they chase the cow. multiple rules unified. step 2: select the shorter rule, rule 2. select the wrong rule. further steps fail to prove the goal. conclusion: unknown. premise confusion error: lambada encountered premise confusion where rule 2 and rule 3 are both unified with the consequent of the goal statement. the model erroneously selects rule 2 with fewer subgoals, leading to further steps that fail to prove the sub-goal. ## conclusion we propose the bidirectional chaining method, bi-chainer, to overcome the limitations of existing unidirectional chaining methods for complex logical reasoning. by dynamically switching to depthfirst reasoning in the opposite direction when faced with multiple branching options, bi-chainer leverages intermediate reasoning results to enhance the reasoning process. in the experiments, bi-chainer demonstrates substantial accuracy improvements over unidirectional chaining frameworks on challenging datasets. it also improves the accuracy of intermediate proof steps and reduces the average number of inference calls, resulting in more efficient and accurate reasoning.