LAMBADA: Backward Chaining for Automated Reasoning in Natural Language

Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers, pages 6547–6568 July 9-14, 2023 ©2023 Association for Computational Linguistics LAMBADA: Backward Chaining for Automated Reasoning in Natural Language Mehran Kazemi, Najoung Kim, Deepti Bhatia, Xin Xu, Deepak Ramachandran Google Research {mehrankazemi, njkim, bhatiad, xxujasime, ramachandrand}@google.com Abstract Remarkable progress has been made on auto- mated 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 for- ward 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 rea- soning. The classical automated reasoning lit- erature has shown that reasoning in the back- ward direction (i.e. from the intended con- clusion 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 infer- ence. We show that LAMBADA achieves siz- able accuracy boosts over state-of-the-art for- ward reasoning methods on two challenging logical reasoning datasets, particularly when deep and accurate proof chains are required. 1 Introduction Automated reasoning, the ability to draw valid con- clusions from explicitly provided knowledge, has been a fundamental goal for AI since its early days (McCarthy, 1959; Hewitt, 1969). Further- more, logical reasoning, especially reasoning with unstructured, natural text is an important build- ing block for automated knowledge discovery and holds the key for future advances across various sci- entific domains. While in recent years tremendous progress has been made towards natural language understanding thanks to pretrained language mod- els (LMs) (Brown et al., 2020; Chowdhery et al., 2022, i.a.,), the performance of these models for logical reasoning still lags behind (Rae et al., 2021; Creswell et al., 2023; Valmeekam et al., 2022) com- pared to the advancements in other areas such as reading comprehension and question-answering. 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. Goal: ● Eric is nice? Label ● Proved Fact Check Cache Rule Selection Decompose Rule6 Eric is nice Eric is red Rule Selection Decompose Eric is big Eric is young Rule3 Cache Eric is big Cache Eric is cold Eric is rough Rule Selection Decompose Rule4 Decompose Rule5 Eric is round Rule Selection Eric is cold Pruned …

Content truncated to 500 words