Deductive Additivity for Planning of Natural Language Proofs (2023)

Abstract: Current natural language systems designed for multi-step claim validation typically operate in two phases: retrieve a set of relevant premise statements using heuristics (planning), then generate novel conclusions from those statements using a large language model (deduction). The planning step often requires expensive Transformer operations and does not scale to arbitrary numbers of premise statements. In this paper, we investigate whether efficient planning heuristic is possible via embedding spaces compatible with deductive reasoning. Specifically, we evaluate whether embedding spaces exhibit a property we call deductive additivity: the sum of premise statement embeddings should be close to embeddings of conclusions based on those premises. We explore multiple sources of off-the-shelf dense embeddings in addition to fine-tuned embeddings from GPT3 and sparse embeddings from BM25. We study embedding models both intrinsically, evaluating whether the property of deductive additivity holds, and extrinsically, using them to assist planning in natural language proof generation. Lastly, we create a dataset, Single-Step Reasoning Contrast (SSRC), to further probe performance on various reasoning types. Our findings suggest that while standard embedding methods frequently embed conclusions near the sums of their premises, they fall short of being effective heuristics and lack the ability to model certain categories of reasoning.

## introduction one way to justify the truth of a statement is to give an explanation building logically towards that statement based on deduction from shared premises. the ways facts can be combined through reasoning are numerous, including many different modes of deduction like syllogism or modus tollens. this process can be automated with natural language processing, using systems to generate natural language proofs that use evidence to derive a claim through a structured argument. large language models (llms) like gpt4 (openai, 2023) have exhibited impressive performance in reasoning tasks. however, these models can still make unsound inferences @xcite @xcite . one reason for these errors is that models may fail to plan reasoning effectively. llms do not have explicit planning capabilities: they generate conclusions in a way that conflates lexical choice and decisions of what content to generate, and no alternatives are materialized in typical greedy or sampling-based llm inference. a recent line of work @xcite @xcite explores how to decouple these stages. however, what is still missing is a scalable method for doing planning in these kinds of natural language reasoning settings: past work involves early-fusion invocation of pretrained lms @xcite and does not scale to thousands of premises. this work explores the feasibility of planning the reasoning process directly in a vector space, where combining statements and retrieving similar statements can be efficiently implemented as addition and cosine similarity, respectively. we introduce deductive additivity (da), a property of an embedding space necessary to enable this planning. a visualization of an embedding space with the deductive additivity property is shown in figure 1 . each piece of evidence is embedded into a fixed-size vector, and the combined embeddings of two facts should be close to embeddings of statements that are entailed from those two facts via deduction. this property can help us plan when we are trying to derive a goal statement based on premise statements. new facts that bring us closer to that goal should be explored in the deductive reasoning process, so this vector space provides a natural heuristic: we want to find fact embeddings that, when summed, achieve the highest dot product with the encoding of our goal. crucially, the vector-based nature of this heuristic facilitates rapid retrieval through efficient search algorithms. our experiments test both off-the-shelf embeddings (e.g., simcse @xcite ) as well as embeddings that are explicitly tuned for deductive additivity. first, we conduct intrinsic evaluations to see whether embeddings of standard encoders exhibit deductive additivity. we then test how well the method performs as a search heuristic on the natural language proof generation datasets entailmentbank @xcite and everyday norms: why not @xcite . finally, we create the single-step reasoning contrast (ssrc) dataset to benchmark each method on how well they model different reasoning categories, like syllogism or modus tollens, and how robust they are to common errors in reasoning, like negation. our main contributions are threefold: (1) we propose a novel method for planning reasoning steps over a collection of facts purely based on vector arithmetic. (2) we show that several embedding methods have promise for deductive additivity but do not fully meet the properties required for planning in natural language deduction scenarios even when explicitly fine-tuned for it. (3) we present a new dataset meant to help diagnose and identify areas where deduction planning methods are underperforming across a range of different reasoning categories. ## problem description and motivation here we introduce the problem of proof generation, the system we use to generate proofs and deductive additivity. ## heuristics and datasets to measure the performance of using deductive additivity as a proof generation heuristic, we explore five heuristics and three datasets. ## discussion vector-based methods are not sufficient to capture all information for planning deductions. we've found that vector-based methods can represent complex reasoning but fall short in planning reasoning steps when compared to earlyfusion premise rankers like scsearch. our results suggest a more complex and structured approaches may be necessary for step-by-step systems. skewed datasets provide optimistic benchmarks for weaker models. our results focused on the t2 setting because we discovered that a bm25 + scsearch pipeline did quite well and scaled to large numbers of premises. however, we believe this is an optimistic result and may not scale to production settings where claims may require more complex deductions that are less sensitive to lexical overlap. developing datasets with more complex reasoning and benchmarking in real production settings is a focus for future work. training for deductive additivity can harm performance. we found that training deductive additivity directly improves categories of reasoning prevalent in the training dataset while harming other categories. both larger and more diverse datasets may be a solution for this problem, but gpt3 embeddings already show deductive additivity without explicitly training for it. developing different training objectives that result in embeddings with deductive additivity is another focus for future work. ## related work our work follows from models and methods done in the question answering domain where models are required to generate an answer or select evidence that leads to the answer through "multi-hop" reasoning @xcite @xcite . although these end-to-end methods can be used in proof generation, understanding the underlying reasoning of the decisions being made is impactful for understanding the affordances of the model @xcite . step-by-step methods have been looked at for proof generation, detangling planning and reasoning into separate subsystems that work together as a whole when proving a claim @xcite @xcite @xcite @xcite . there has also been work on using similar modular systems in answering questions with a knowledge base and different types of embeddings @xcite @xcite . our work extends from this literature, focusing on exploring alternative heuristics for natural language deduction planning entirely in embedding space by tapping into the property of deductive additivity. we also follow work being done in retrieval, which focuses on finding evidence from a large corpus that would help answer a query. state-of-the-art retrieval methods involve encoding the corpus into vector indexes that can be used to calculate the cosine similarity of an encoded query @xcite @xcite . sparse encoders, like bm25, have also been used to help reduce the search space for relevant passages @xcite . however, none of the methods tap into the deductive additivity property in their embedding spaces and instead encode the query to find relevant passages and then re-encode the query with the appended passages to find additional relevant passages. we consider this to be similar to earlyfusion premise rankers in the proof generation task. another line of relevant work deals with understanding reasoning errors from language models, like the detection of logical fallacies in text @xcite . we further this line of work with the ssrc dataset, building a contrast set @xcite for reasoning targeting certain types of deductions and common reasoning errors. ## conclusion in this work, we have explored the property of deductive additivity in sentence embedding spaces. results show that off-the-shelf sentence encoders exhibit the property somewhat; however, when used as heuristics in natural language proof generation, they are only slightly more successful than bm25. furthermore, we see that fine-tuning for deductive additivity does not lead to better reasoning capabilities of the embedding space, and we posit that a large contributor to this could be skewed datasets. we introduced the single-step reasoning contrast dataset, which shows that these same skewed datasets provide over-optimistic results for inferior methods harming our ability to benchmark systems for their use in production settings. lastly, we've shown that early-fusion premise rankers like scsearch still outperform vector-based approaches. however, their ability to scale to more diverse reasoning datasets that are less sensitive to lexical overlap is still an open question for future work.