LAMBADA: Backward Chaining for Automated Reasoning in Natural Language
Mehran Kazemi, Najoung Kim, Deepti S. Bhatia, Xin Xu, Deepak Ramachandran · 2023
Remarkable progress has been made on automated reasoning with natural text, by using Language Models (LMs) and methods such as Chain-of-Thought and Selection-Inference.These techniques search for proofs in the forward direction from axioms to the conclusion, which suffers from a combinatorial explosion of the search space, and thus high failure rates for problems requiring longer chains of reasoning.The classical automated reasoning literature has shown that reasoning in the backward direction (i.e. from the intended conclusion to supporting axioms) is significantly more efficient at proof-finding.Importing this intuition into the LM setting, we develop a Backward Chaining algorithm, called LAM-BADA, that decomposes reasoning into four sub-modules.These sub-modules are simply implemented by few-shot prompted LM inference.We show that LAMBADA achieves sizable accuracy boosts over state-of-the-art forward reasoning methods on two challenging logical reasoning datasets, particularly when deep and accurate proof chains are required. Facts:1. Rough and cold that is what they say about Blue Bob. 2. Eric, who is relatively young, is also pretty big and tends to be cold.3. Fred is green and cold too.4. For being so cold, it's good Harry can remain nice.Rules: 1. Rough, cold people are blue.2. Big, kind folks are green ones.3.If a person is big, rough, and cold, they are also red. 4. Most round and cold people are often rough.5. Cold, young people are also certain to be rough people.6.An individual who is big, red and young is also a nice individual.