Natural Language Deduction through Search over Statement Compositions (2022)

Abstract: In settings from fact-checking to question answering, we frequently want to know whether a collection of evidence (premises) entails a hypothesis. Existing methods primarily focus on the end-to-end discriminative version of this task, but less work has treated the generative version in which a model searches over the space of statements entailed by the premises to constructively derive the hypothesis. We propose a system for doing this kind of deductive reasoning in natural language by decomposing the task into separate steps coordinated by a search procedure, producing a tree of intermediate conclusions that faithfully reflects the system’s reasoning process. Our experiments on the EntailmentBank dataset (Dalvi et al., 2021) demonstrate that the proposed system can successfully prove true statements while rejecting false ones. Moreover, it produces natural language explanations with a 17% absolute higher step validity than those produced by an end-to-end T5 model.

## introduction when we read a passage from a novel, a wikipedia entry, or any other piece of text, we gather meaning from it beyond what is written on the page. we make inferences based on the text by combining information across multiple statements and by applying our background knowledge. this ability to synthesize meaning and determine the consequences of a set of statements is a significant part of natural language understanding. humans are able to give step-by-step explanations of the reasoning that they do as part of these processes. however, approaches that involve endto-end discriminative fine-tuning of pre-trained language models have no such notion of step-bystep deduction; these models are black boxes and do not offer explanations for their predictions. this limitation prevents users from understanding and paper is recyclable cardstock is a type of paper recyclable means old material can be turned into new material cardstock is recyclable old cardstock can be turned into new cardstock premises goal new cardstock can be produced from old cardstock entails intermediate conclusions accommodating models' affordances @xcite . a simple way of representing this kind of reasoning process is through an entailment tree @xcite : a derivation indicating how each intermediate conclusion was composed from its premises, exemplified in figure 1 . generative sequence-to-sequence models can be fine-tuned to carry out this task given example trees @xcite . however, we argue in this paper that this conflates the generation of individual reasoning steps with the planning of the overall reasoning process. an end-to-end model is encouraged by its training objective to generate steps that arrive at the goal, but it is not constrained to do so by following a sound structure. as we will show, the outputs of such methods may skip steps or draw unsound conclusions from unrelated premises while claiming a hypothesis is proven. generating an explanation is not enough; we need explanations to be consistent and faithfully reflect a reasoning process to which the model commits @xcite . this paper proposes a system that factors the reasoning process into discrete search over intermediate steps. the core of our system is a winter has the least sunlight @xmath0 the united states is located in the northern hemisphere the northern hemisphere has the least amount of sunlight during the month of december y 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " f y j 7 w w r 8 m s p + g v i y t x w 9 o 2 2 h n 5 @xmath1 the united states has the least sunlight during the month of december u a s r 4 z x j 9 t f 2 n v + z w q n g 6 7 d p p a 4 o u d 8 f b c l j w d k e 9 4 v y 7 5 z 9 9 7 9 b w c p n u e p n z x 9 n j h 8 v l j f j q l d k o i x 8 i l b i n k w 0 6 v m m t o l u l i s e k 7 x y d w b t l 9 / p 1 k x i v + q 6 5 l g a m 9 y l j g c t a h q 4 m d o m y 4 e 1 p d j 1 t q t j a r l 4 z / 3 t j 1 2 r p g m w 9 3 x a r j e 0 b z 5 i z 6 2 1 + l q b p k 4 8 s a e o z s x 1 z w 4 + a / h n u 8 6 3 7 w z v d e g + r x v j b a o 9 0 n r 0 d x t x x g f p i p g u y o j k y w u e 7 b e x 8 b 1 r r c a b r o 4 r b n j z 4 v 8 d k 3 r y o i 5 x h / w n v d 3 y a j 2 s u c d n 1 f a k e r q x b o o l q p 9 r 9 r x g 6 v m h n p w i s p f s 0 y u 8 i a g b u z y u b u 3 / r w t h b k m h v k h z c k 1 7 n n r g q 0 w s t u i m c 5 u i + q m 1 p h / 0 s j k z 6 d x w / k y 0 j q n u 0 j z x a e u y p d v m g w s e s 1 r a z c r z p q k y s w w m g j z u 4 5 z g n 9 z 5 n t g f b j + 1 a 0 + z y z n 5 / t 1 h i a x 4 c u y a x / m w r l 4 b x z g c y j 1 y v p g r a y 1 p b e / 2 9 / s c g e 1 r x 3 o e f g r 7 p q 3 i j / l b @xmath2, @xmath3, @xmath4, @xmath5 a s r 4 z x j 9 t f 2 n v + z w q n g 6 7 d p p a 4 o u d 8 f b c l j w d k e 9 4 v y 7 5 z 9 9 7 9 b w c p n u e p n z x 9 n j h 8 v l j f j q l d k o i x 8 i l b i n k w 0 6 v m m t o l u l i s e k 7 x y d w b t l 9 / p 1 k x i v + q 6 5 l g a m 9 y l j g c t a h q 4 m d o m y 4 e 1 p d j 1 t q t j a r l 4 z / 3 t j 1 2 r p g m w 9 3 x a r j e 0 b z 5 i z 6 2 1 + l q b p k 4 8 s a e o z s x 1 z w 4 + a / h n u 8 6 3 7 w z step deduction module that generates the direct consequence of composing a pair of statements. this module is used as a primitive in a search procedure over entailed statements, guided by a learned heuristic function. by decoupling the deduction itself from the search over statement combinations, our system's design ensures that each step's conclusion builds on its inputs, avoiding the pitfalls of end-to-end generation. we evaluate our method on the entailmentbank dataset @xcite . thanks to our system's factored design and its ability to capitalize on additional semi-synthetic single step data @xcite , we observe that 82% of the reasoning steps produced by our approach are sound, a 17% absolute increase compared to an end-to-end model replicated from prior work. our contributions are: (1) a factored, interpretable system for natural language deduction, separating the concerns of generating intermediate conclusions from those of planning entailment tree structures; (2) exploration of several search heuristics, including a learned goal-oriented heuristic; (3) comparison to an end-to-end model from prior work @xcite in two settings of varying difficulty. ## problem description and motivation the general setting we consider is shown in figure 2 . we assume we are given a collection of evidence sentences @xmath6. . . x n } 1 and a goal statement g. we want to construct an entailment tree deriving g from x. an entailment tree is a tree of statements with the property that each statement in the settings we consider in this paper, n does not exceed 25. however, this is not a hard limit imposed by our approach, and for very large premise sets, a retrieval system could be used to prune the premise set to a manageable size. crucially, we assume that the intermediate nodes of this tree must be generated and are not present in the input premise set x. this condition differs from prior work on question answering with multihop reasoning @xcite or models that build a proof structure but do not generate new statements @xcite . we therefore require a generative step deduction model s to produce intermediate conclusions given their immediate children, a concept explored by @xcite and @xcite . s yields a distribution p s (y | x 1 . . . x m ) over step conclusions y conditioned on inputs x i . in our approach, we assume that each step has exactly @xmath7. some nodes in our evaluation dataset, entailmentbank, have more than two children, but in preliminary investigation we found it possible to express the reasoning in these steps in a binary branching format. we do not apply this arity constraint to baseline models. ## methods our proposed system consists of a step model s, a search procedure involving a heuristic h, and an entailment model which judges whether a generated conclusion entails the goal. an overview of the responsibilities and task data required by each module is presented in ## experimental setup our experiments assess whether our scsearch system, which factors the deduction process into separate step generation and search modules, can do better than end-to-end baselines on two axes: (1) proving correct (and only correct) goals, and (2) producing more consistent entailment steps in the tree. ## results the results of our experiments on task 1 and task 2 are shown in ## related work our work reflects an outgrowth of several lines of work in reading comprehension and textual reasoning. multi-hop question answering models @xcite @xcite , inter alia) also build derivations linking multiple statements to support a conclusion. however, these models organize selected premises into a chain or leave them unstructured as opposed to composing them into an explicit tree. the nlprolog system @xcite ) frames multi-hop reading comprehension explicitly as a proof process, performing proof search using soft rule unification over vector representations of predicates and arguments. similar backward search ideas were used in @xcite . prover @xcite and proofwriter @xcite also frame natural language deduction as proof search, although both systems are evaluated in a synthetic domain of limited complexity. @xcite also use synthetic data to improve reasoning models through midtraining, although the improvements they observe are limited to premise selection performance. @xcite and @xcite propose systems which perform single-sentence natural language inference through proof search in the natural logic space. our work also relates to earlier efforts on natural logic @xcite but is able to cover far more phenomena by relaxing the strict constraints of this framework. finally, the leap of thought system @xcite tackles some related ideas in a discriminative reasoning framework. the recent chain-of-thought @xcite ) and scratchpads @xcite methods also generate intermediate text as part of answer prediction. however, like the end-to-end baseline we consider, these techniques are free to generate unsound derivations. published results with these techniques are strongest for tasks involving mathematical reasoning or programmatic execution, whereas on textual reasoning datasets like strategyqa @xcite they only mildly outperform a few-shot baseline. ## discussion and conclusion in this work, we propose a system that performs natural language reasoning through generative deduction and heuristic-guided search. we demonstrate that our system produces entailment trees that are more internally consistent than those of an end-to-end model, and that its factored design allows it to successfully prove valid goals while being unable to hallucinate trees for invalid goals. we believe that this modular deduction framework can be readily extended to empower future reasoning systems.