What are the prior approaches proposed to improve faithfulness of the reasoning steps generated by LLMs and what tasks are they applied on?
However, the generated steps could be unfaithful (Wei et al., 2022b; Zelikman et al., 2022; Creswell et al., 2022). To tackle this issue, faithful question-answering (FQA) pro-
poses to answer questions based on the faithful reasoning steps (Tafjord et al., 2022; Creswell and Shanahan, 2022; Weir and Durme, 2022; Bostrom et al., 2022), where each step is a valid entailment and the intermediate conclusions support the answer. Existing FQA methods typically adopt a step-wise approach. To decide the next step, their strategy (e.g., overgenerate-and-filter of Entailer (Tafjord et al., 2022) and beam search of Selection-Inference (SI) (Creswell and Shanahan,2022)) might lack foresight and could be inadequate for complex questions.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
We present an approach for systematic reasoning that produces human interpretable proof trees grounded in a factbase. Our solution re-sembles the style of a classic Prolog-based inference engine, where we replace handcrafted rules through a combination of neural language modeling, guided generation, and semi-parametric dense retrieval. This novel reasoning engine, N ELLIE , dynamically instantiates interpretable inference rules that capture and score entailment (de)compositions over natural language statements. N ELLIE provides competitive performance on scientiﬁc QA datasets requiring structured explanations over multiple facts.
[{"first":"Nathaniel","last":"Weir","middle":[]},{"first":"Benjamin","last":"Durme","middle":["Van"]}]
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Our goal is a question-answering (QA) system that can show how its answers are implied by its own internal beliefs via a systematic chain of reasoning. Such a capability would allow better understanding of why a model produced the answer it did. Our approach is to recursively combine a trained backward-chaining model, capable of generating a set of premises entailing an answer hypothesis, with a verifier that checks that the model itself believes those premises (and the entailment itself) through self-querying. To our knowledge, this is the first system to generate multistep chains that are both faithful (the answer follows from the reasoning) and truthful (the chain reflects the system's own internal beliefs). In evaluation using two different datasets, users judge that a majority (70%+) of generated chains clearly show how an answer follows from a set of facts - substantially better than a high-performance baseline - while preserving answer accuracy. By materializing model beliefs that systematically support an answer, new opportunities arise for understanding the model's system of belief, and diagnosing and correcting its misunderstandings when an answer is wrong.
[{"first":"Oyvind","last":"Tafjord","middle":[]},{"first":"Bhavana","last":"Mishra","middle":["Dalvi"]},{"first":"Peter","last":"Clark","middle":[]}]
Faithful Reasoning Using Large Language Models
Although contemporary large language models (LMs) demonstrate impressive question-answering capabilities, their answers are typically the product of a single call to the model. This entails an unwelcome degree of opacity and compromises performance, especially on problems that are inherently multi-step. To address these limitations, we show how LMs can be made to perform faithful multi-step reasoning via a process whose causal structure mirrors the underlying logical structure of the problem. Our approach works by chaining together reasoning steps, where each step results from calls to two fine-tuned LMs, one for selection and one for inference, to produce a valid reasoning trace. Our method carries out a beam search through the space of reasoning traces to improve reasoning quality. We demonstrate the effectiveness of our model on multi-step logical deduction and scientific question-answering, showing that it outperforms baselines on final answer accuracy, and generates humanly interpretable reasoning traces whose validity can be checked by the user.
[{"first":"Antonia","last":"Creswell","middle":[]},{"first":"Murray","last":"Shanahan","middle":[]}]
Natural Language Deduction through Search over Statement Compositions
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.
[{"first":"Kaj","last":"Bostrom","middle":[]},{"first":"Zayne","last":"Sprague","middle":[]},{"first":"Swarat","last":"Chaudhuri","middle":[]},{"first":"Greg","last":"Durrett","middle":[]}]
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Recent work has explored whether neural NLP models can emulate the behavior of expert systems (Jackson, 1986;Metaxiotis et al., 2002), i.e., symbolic inference engines that reason over a knowledge base (KB) of facts and axioms expressed in a logical formalism. Expert systems are appealing in part for their explainable behavior; they make decisions through the process of systematically constructing a well-formed symbolic proof predicated upon explicit knowledge carefully enumerated by an engineer under consultation with a domain expert.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
As expert systems are brittle and can be prohibitively expensive and time-consuming to curate (Musen and Van der Lei, 1988), the AI community has begun to explore neuro-symbolic mechanisms that incorporate large language models (LLMs)-which might reason over natural language (NL)-into otherwise symbolic reasoning procedures. Reasoning over NL representations eschews the need to adhere to a single symbolic formalism and introduces the possibility of using the inferential power of pretrained models. It has been suggested that LLMs can perform something Prove(plants use light to produce carbohydrates via photosynthesis) 
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Factbase Unification Module
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Dynamic Rule Generator
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Prove(chlorophyll is used for absorbing light energy by plants)
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Factbase Unification Module
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Prove(photosynthesis is a source of food for the plant by converting carbon dioxide, water, and sunlight into carbohydrates) Figure 1: NELLIE uses retrieval-and templateconditioned generation to dynamically instantiate rules during a neuro-symbolic backward chaining search for proofs grounded in an semi-structured NL factbase. akin to logical reasoning  and can implicitly capture the world knowledge reflected in the language corpora on which they are trained (Petroni et al., 2019), and that such world knowledge can be queried, retrieved, and reasoned about under careful supervision (Shwartz et al., 2020;Talmor et al., 2020). However, such reasoning is hardly interpretable, as LLMs are notoriously black box systems. We are only in the early stages of probing models for what they might "believe" about the world, let alone rely upon such belief during systematic reasoning (Dalvi et al., 2022).
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
This motivates our pursuit of an inference procedure that uses LLMs and their reasoning capacity, but which constructs explicit knowledgegrounded proofs that are interpretable to humans and grounded in verifiable facts. This work introduces NELLIE, the Neurosymbolic Large LM Inference Engine, a QA system which leverages recent LLMs as proposal functions in the search of proofs grounded in an externally provided NL factbase. The "symbols" that our neuro-symbolic inference engine reasons over are mostly free-form NL sentences. Rather than require a knowledge engineer to carefully write hundreds of inference rules as in the classical expert system setting, NELLIE employs neural generation and dense retrieval as dynamic rule generators (DRGs; Kalyanpur et al., 2021), producing conjunctions of premises that, if themselves proved, would prove an input NL query via compositional entailment. An example of this procedure is depicted in Figure 1.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Our DRGs make use of the semi-structured content in NELLIE's NL factbase using a pair of methods for knowledge-infused text generation: forced decoding of sentences acquired via learnt dense retrieval, and guided generation conditioned on infilling templates that reflect inference-supporting syntactic types drawn from the tables underlying the KB (Jansen et al., 2018). These techniques bias the proof search towards trees that are likely provable given the available facts, reflecting the capacity for LMs to infuse high level domain structure into text-based reasoning wherever it is available.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
The system is built upon a backward chaining symbolic theorem prover written in Prolog, but ultimately requires only a few handwritten meta-rules specifying the high-level structure of NL-based inference rules. The meta-rules pertain to checking for entailment of a hypothesis against the provided factbase, or decomposing it into a conjunction of support facts to recursively prove. In order to treat NL sentences as if they were symbols in a purely symbolic proof search algorithm, we use weak unification (Sessa, 2002;Weber et al., 2019) between sentences using neural encoder models fine-tuned for semantic comparison via embedding cosine similarity (Reimers and Gurevych, 2019).
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
An appealing characteristic of NELLIE is its heavy modularity. We use a heterogeneous mixture of transformer-based expert models for generating, retrieving, and verifying premises for entailment hops, which are formalized structurally as conjunctive Prolog-based backward chaining search steps. We strive to compartmentalize and separately optimize the generative and discriminative decision points of the reasoning process: a seq2seq model proposes NL statements via stochastic sampling, which are then verified as logically coherent using a mixture of filter models trained on variants of natural language inference (NLI).
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
The resulting inference engine shows upon evaluation on a pair of Science QA datasets to produce coherent and interpretable inference proofs akin to the compositional entailment trees of Entailment-Bank (Dalvi et al., 2021), while performing competitively given the constraint that the model must "explain its work" by grounding a logical decision proof in an external NL factbase.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Our analysis explores the impact of NELLIE's knowledge-guided generation techniques on proof search and QA performance. We identify avenues for future improvement of modular components, elucidated by granular consideration of error cases.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Contribution This work introduces NELLIE, a backward-chaining inference engine that reasons over natural language statements using pretrained language models, guided generation, and dense retrieval over explicit knowledge. While recent literature on NL explanation tree generation has considered the task of proving true statements given small sets of gold support facts (Dalvi et al., 2021;Bostrom et al., 2022), or generating proofs grounded in model beliefs (Dalvi et al., 2022), we instead consider a neoclassical expert system scenario in which an inference engine must consider and score a set of alternative answers to a question, but all the system's decisions must be structured trees fully grounded in verified NL facts from an external tablestore. In this challenging scenario, NELLIE achieves nontrivial, fully interpretable performance on QA datasets whose answers are not guaranteed to have fully-KB-grounded proof trees.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Reasoning over NL NELLIE's systematic reasoning is related to recent NLP approaches that decompose problems into sequences of modular operations.  introduce a neural module network (NMN; Andreas et al., 2016) that performs QA using separate modules to perform text span extraction and arithmetic operations. Khot et al. (2021) introduce another NMN variant that decomposes a question into a sequence of simpler ones answerable by different existing models. Systematic question decomposition is also explored in Talmor  Systematic Explanation Generation A series of recent work has tackled structured explanation generation, in which a high-level hypothesis is supported by a reasoning chain of systematic inference operations over natural language. One strategy, coined "chain of thought" prompting Kojima et al., 2022), is to elicits freeform intermediate inference hops from LMs before they generate a final answer. The recent Entail-mentBank dataset (Dalvi et al., 2021) has driven research towards the construction of explanation trees, challenging models to reconstruct stepwise entailment proofs of a statement using a set of provided support facts. This direction builds upon a previous batch of approaches for explainable reasoning that aim to retrieve a set of support statements from a knowledge store that justify a decision, stopping short of explaining their role in logical entailment (Pan et al., 2019;Jansen and Ustalov, 2019;Yadav et al., 2019;Valentino et al., 2020;Thayaparan et al., 2021).
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Components of NELLIE share conceptual similarities with concurrent approaches for logical explanation tree reconstruction (Bostrom et al., 2022;Hong et al., 2022). Ribeiro et al. (2022) use a similar iterative retrieval-conditioned premise generation. Yang et al. (2022); Dalvi et al. (2022) also make use of entailment classifiers to filter candidates. Few tree generation approaches consider the harder scenario of multiple-choice QA as NELLIE does, opting instead to focus on the reconstruction task given gold support facts. Dalvi et al. (2022) do consider the harder task; their work is most similar to ours. They also propose a backward chaining explainable QA system that generates entailment trees, though theirs are not grounded in humanverified facts. Theirs is a greedy search driven by heuristic values based upon internal model belief of factuality, complementary to NELLIE's use of guided and retrieval-conditioned generation.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
A logical expert system proves a propositional query against a theory comprised of facts and inference rules, generally given in the form of Horn clauses. Upon finding a rule whose head can unify with the query, a depth-first backward chaining algorithm such as used in Prolog solvers will, upon performing variable substitution, recursively attempt to prove the terms in the rule's antecedent. For example, a
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Figure 2: System diagram for NELLIE. An off-the-shelf theorem prover searches for proofs of the query PROVE(h), where symbol h is an NL hypothesis string translated from a QA pair by a neural seq2seq. The prover is provided a set of meta-axioms that invoke neural retrieval, entailment, and generation predicates to dynamically instantiate inference rules in NL using the external factbase.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
disease classification system might prove query CONTAGIOUS(flu) via facts CONTAGIOUS(influenza) and OTHERNAME(flu, influenza), and conjunctive rule
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
It does so by unifying CONTAGIOUS(flu) with CONTAGIOUS(X) and then recursively unifying the terms in the rule body with their matching facts. Here, flu is an object symbol, CONTAGIOUS is a predicate symbol, and X is a variable. See Russell and Norvig (2010) Neural Predicates While most declarative predicates have meaning only in the context of userdefined inference axioms, others can call external modules that produce values for their arguments and/or determine the truth value of the predicate. NELLIE makes heavy use of this feature for defining neural model-invoking predicates. In the above example, we might train a seq2seq to produce other names for a disease Y , turning OTHERNAME(Y + , X − ) 2 into a neural predicate. This mechanism opens up the capacity to introduce externally-defined object symbols, e.g. seq2seqgenerated NL, into the engine's vocabulary.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Weak Unification In classical backward chaining, a unification operator is used to make two logical atoms syntactically equivalent. Unification can only occur between two atoms if they are of the same arity and have no unequal ground literals in the same argument position. Issues arise when literals are NL sentences, which can be syntactically distinct but semantically equivalent. In order to consider free-form NL as part of the backward chaining algorithm, Weber et al. (2019) propose to replace hard unification with a softer weak unifica-2 In Prolog syntax, '+' denotes inputs, '−' outputs. tion operator, which allows for the unification of any arity-sharing atoms regardless of exact match between symbols. This is accomplished using a similarity function s 1 ≈ θ s 2 ∈ [0, 1]. For comparing atoms with multiple symbols, Weber et al.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
(2019) estimate a unification score as the aggregation of pairwise similarity scores. The score of an entire proof is taken to be the minimum of unification scores across all steps in the proof tree.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Depicted in Figure 2, NELLIE is comprised of: An external factbase (some {f 1 , . . . f n }); a module that converts a QA pair to a hypothesis; a fact retrieval module; and a dynamic rule generation module. The latter three components make use of a suite of neural models to propose, verify, and score inferences. In our experiments, we use as the factbase the WorldTree V2 corpus (Xie et al., 2020), a set of 81 relational tables whose rows concatenate into 9K inference-supporting science facts.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Given a multiple-choice question, NELLIE takes a candidate answer and converts the QA pair into a single hypothesis statement h using a neural model for Question to Declarative Sentence conversion (QA2D; Demszky et al., 2018). It then attempts to prove h against its knowledge base. An example conversion is shown in §B. For each alternative, we enumerate n proofs using a timecapped backward chaining search, and then take as the system's answer the alternative with the overall highest-scoring proof. This approach is similar to that of Dalvi et al. (2022).
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
NELLIE dynamically instantiates inference rules given a goal hypothesis statement to prove. The structure of such a rule is strikingly simple, emulating that of one of the following templates:
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Via template I, the system proves the hypothesis by finding another Fact stored in its knowledge store that entails the hypothesis. Via template II, it enumerates a pair, Fact1 and Fact2, both either stored in the knowledge store or themselves recursively proved, such that the pair in conjunction entail the hypothesis. Template I is given higher precedence than II, 3 yielding a rather intuitive highlevel procedure: NELLIE first looks up the hypothesis against its factbase, searching for an entailing premise. If it does not find one, it decomposes the hypothesis into a pair of statements, themselves needing to be proved. Concretely, for an input hypothesis h, we define the predicate PROVE(h) that serves as the primary goal term. We define the following rules, which serve as the inferential backbone of NELLIE and make use of the neural predicates RETRIEVE, ENTAILS and RULEGEN:
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
At each step in the backward-chaining search, NELLIE's Prolog engine will attempt unify a query with the head of one of these three rules.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
For all factbase facts f , PROVE(f ) is vacuously true. We consider PROVE(h) to weakly unify with some PROVE(f i ), as is implicit in rule 1a, with unification score cos(θ 1 (h), θ 1 (f i )) for sentence embedding model θ 1 . The predicate RETRIEVE proposes candidate f i 's given h using a FAISS (Johnson et al., 2019)-based nearest-neighbor lookup according to θ 1 . To promote logical coherence, we apply a set of differently-trained neural RTE models as filters that iteratively whittle away f i candidates that are not classified as entailing h.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
If NELLIE fails to retrieve an entailing fact for hypothesis h as decided by its set of RTE filters, it attempts to decompose h into a pair of entailing support statements using stochastic sampling from a neural seq2seq model to propose candidates. In our experiments, we use nucleus sampling (Holtzman et al., 2019) (p=.95). The predicate RULEGEN(h, f 1 , f 2 ) prompts an encoderdecoder model trained on h → f 1 , f 2 pairs. The space of potential decompositions of a given hypothesis is massive, and the candidates sampled from the generator will depend heavily upon the dataset upon which it was trained. As we want to bias the proof search towards statements that can be grounded in the facts of NELLIE's factbase, we adopt a two-pronged approach to dynamic rule generation, illustrated in inference rules 2a and 2b.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Structurally Guided Generation In 2a, the DRG predicts f 1 , f 2 in sequence. Part of the set of candidate pairs results from regular stochastic sampling conditioned on h. The rest is sampled using template-guided generation, which takes advantage of the semi-structured nature of NELLIE's factbase, WorldTree V2. The WorldTree tables correspond to types of facts with similar syntax and semantics that are likely to support systematic inference. Each table can be viewed as an n-ary relation of content columns whose values are structurally similar text spans. For example, the Taxonomic relation has the columns (some not always used):
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
<A/an>, [HYPONYM], <is a kind of>, <SCOPE1>,
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
[HYPERNYM], <for>, [PURPOSE]. Rows from the table include a bird is an animal and a seed is a kind of food for birds.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
The DRG model is a seq2seq model finetuned to accept an optional template specifying this sort of semi-structured language. It can accept any arbitrary masked infilling template (e.g. <mask> is a kind of <mask>, akin to those used to pretrain recent LLMs Raffel et al., 2020)), and it will propose decompositions that reflect such syntax. We only have the DRG model condition on templates for the f 1 fact, as f 2 should follow from f 1 and h without the need for guidance. We thus create a h, t 1 → f 1 , f 2 seq2seq. We feed the model templates drawn from WorldTree's tables, guiding it towards proof steps more likely to be grounded in the factbase. 4 We reuse the same model for non-template-conditioned generation by feeding it an empty template. In practice, we make a pair of generation calls, one that samples m free-generated candidates, and a second that samples n candidates for each of 50 templates, the list of which can be found in §C. 5
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Template t is the sole piece of domain-specific symbolic knowledge infused into NELLIE's NL-centric inference algorithm. The neural LM seamless incorporates this helpful domain structure into a hybrid linguistic/symbolic modality.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Retrieval Conditioned Generation In 2b, rather than rely upon the model to generate a pair of decomposition statments, we immediately ground half of the antecedent by choosing f 1 to be a fact retrieved directly from the factbase using the RETRIEVE predicate. We have the generator force decode f 1 before producing f 2 as normal via nucleus sampling. When NELLIE uses rule 2a, the unification score equals the minimum of the scores for PROVE(f 1 ) and PROVE(f 2 ). For 2b, since f 1 is retrieved, the score equals that of PROVE(f 2 ).
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Filters As stochastic sampling from language models is a particularly noisy process, a large fraction of generated candidates are invalid, meaning that the generated facts would not, even if themselves proved, compositionally entail h. 6 Accordingly, we introduce a suite of compositional entailment verifiers (Khot et al., 2020;Jhamtani and Clark, 2020) that function analogously to the retrieval module's, the models are trained specifically to validate compositional entailment.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Given a query, we allow NELLIE to search for up to t seconds to find up to p proofs of depth d or less. We follow the approach by Weber et al. (2019) of pruning search branches whose unification score is guaranteed to fall below the current best, given our monotonic aggregation function min(·).
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
We train the components of NELLIE to be able to answer questions in the Science QA domain. The different neural modules are trained on reformulations of existing datasets for scientific reasoning. QASC (Khot et al., 2020) and eQASC (Jhamtani and Clark, 2020) are a pair of crowdsourced datasets containing single-hop, two-fact compositional entailment questions. eQASC, an expansion of QASC, comprises 21K positive and 59K negative-labeled (f 1 , f 2 , h) triplets. f 1 and f 2 are drawn from a large store of 17M noisy sentences scraped from science text.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
SciTaiL (Khot et al., 2018) is a textual entailment dataset pulled from a combination of science exam question text and retrieved web sentences.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Question Converter NELLIE's QA2D model is a GPT-J model (Wang and Komatsuzaki, 2021) performing in-context learning using gold hypotheses from EntailmentBank. Given an input q, a pair, we fill the model's 2048-token context with randomly sampled gold (q i , a i , h i ) triplets, then greedily decode the hypothesis.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Retrieval Module The embedding model θ 1 is a SentenceTransformers Siamese BERT-Network encoder (Reimers and Gurevych, 2019) pretrained on the MS MARCO IR corpus (Nguyen et al., 2016), which we fine-tune via ranking loss to maximize the cosine similarity between a hypothesis and its support facts. 7 We gather h, f 1 from the WorldTree, EntailmentBank, and eQASC training sets, then sample random negatives during training.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
The DRG is a T5-Large model (Raffel et al., 2020) fine-tuned on h → [f 1 , f 2 ] pairs drawn from the positive-labeled triplets from the eQASC training set, which are numerous (26K) but noisy, and the binary composition steps from the EntailmentBank training set, which are few (3.8K) but ultimately rooted in facts from WorldTree. To make the DRG able to condition on infilling templates, we adopt the span masking strategy from Raffel et al. (2020) to create a randomly masked versionf 1 of each f 1 in the training set and train the model on h,f 1 → f 1 , f 2 pairs. For each original triplet, we create one training example with a masked template, and one in whichf 1 is an empty <mask>, giving the model the dual capacity for non-template-generation.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
As we desire high fidelity explainable reasoning, we want high precision filtering of generated inference hops. We find that a mixture-of-architectures approach improves towards this goal. For 1-premise filtering for the factbase unification module and 2-premise filtering for the DRG module, we fine-tune a separate pair of models consisting of a SentenceTransformers pretrained Cross-Encoder classifier model and a T5-large sequence model. The former is trained via classification loss, the latter via sequence cross entropy loss. The 1-premise filters are trained on the SciTail dataset, while the 2-premise filters are trained on positive and negative compositional entailment (h, [f 1 , f 2 ]) examples drawn from eQASC and EntailmentBank.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
6 Experimental Setup
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
We evaluate NELLIE on a pair of multiple-choice question-answering datasets constructed so that correct answers are supported by facts in the WorldTree Corpus. We impose a timeout of 90 seconds per answer option and a tree depth of 4.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
EntailmentBank QA We convert the Entail-mentBank test set, initially designed as a test of tree reconstruction, into a QA dataset by retrieving the 339 corresponding multiple-choice ARC questions (233 Easy, 106 Challenge) from which the EntailmentBank hypotheses were originally constructed.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
WorldTree QA We also evaluate on the WorldTree QA test set, a different 1664-question (1177 Easy, 487 Challenge) subset of ARC 8 . Answers are annotated with structured graph explanations containing WorldTree facts.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
EntailmentBank QA (Groundable) Not all questions in either of the described datasets are guaranteed to have a NL proof tree that is rooted fully in WorldTree facts. Annotated explanations for WorldTree questions are not trees, nor are they directed or based on entailment relations. Gold trees from EntailmentBank can have fact leaves that were user-annotated 9 rather than retrieved from WorldTree. To investigate performance of a fully fact-rooted test set, we subselect for evaluation the 109 questions from EntailmentBank whose gold explanation trees are fully grounded.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Metrics The primary performance metric is predicted answer accuracy: whether the model generated a proof of the correct option that scored higher than any other. (If the model produces no proofs, it does not give an answer). We also measure proof precision/recall, where a false positive is a proof of (not the prediction of) a wrong answer, the answered rate measuring whether the model predicted a proof for any option, and the rate at which a correct answer proof was outscored by another option. Results are grouped according to ARC question difficulty. 8 Note that the EntailmentBank question split was directly constructed by annotators based on WorldTree's. The former's train/dev splits are subsets of the latter's train split, and the former's test split is a subset of the latter's dev. 9 Usually this occurs when a fact must be drawn from the question context, e.g., to prove two sticks rubbed together produce heat, the fact there are two sticks is used.   Table 1 shows NELLIE's performance on the QA datasets. We compare accuracy on the WorldTree test set against a pair of recent approaches that construct non-proof-tree explanations: PathNet (Kundu et al., 2019), which constructs linear inference chains by linking entities between support facts, and ExplanationLP (Thayaparan et al., 2021), which extracts explanation subgraphs from retrieved support facts using linear programming. 10 These serve as strong baselines, as they operate in a less constrained scenario in which explanations are not required to be logical entailment-based trees. We find that overall (Ovr) accuracy is substantially above chance (25%) on both datasets, even though neither test set is one in which all questions have fully fact-grounded gold proof trees. We observe that NELLIE performs substantially better (55%) on the groundable subset, and equally well on easy vs challenging groundable questions. Nevertheless, we observe a substantial performance gap between NELLIE and the considered baselines on the WorldTree dataset, logical explanation requirements notwithstanding.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
We find that NELLIE produces an answer (Ans) on about 2/3 of questions in non-groundable test sets. This rate increases if we ablate the system's use of template guidance, which imposes extra 10 We use the performances reported by Thayaparan et al. (2021); their results are on a previous version of WorldTree, which contains 1,077 questions (764 Easy, 313 Challenge).  time cost for DRG calls. In general, NELLIE with template-conditioned generation has higher proof precision (Pr) but lower recall (Re) than without. The opposite trend is observed when we ablate retrieval-conditioned generation; precision increases by around 0.1, but answer rate and proof recall steeply decline. This shows that retrievalconditioned generation is an important factor in guiding the proof search towards correct proofs. Meanwhile, the results suggest that template conditioning biases the proof search away from inference hops that fool the system's entailment filters; ablating templates effectively doubles the out scored rate by which NELLIE produces a higher-scoring proof of a wrong answer than of the correct one. Such a high rate suggests that NELLIE has ample room for QA performance improvement simply by improving the effectiveness of its entailment filters, an issue we discuss further in §7.3.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
NELLIE's performance on the QA task is potentially confounded by errors by its QA2D model, 
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Q: Which statement explains why a mother's unhealthy diet during pregnancy is harmful to her embryo's development? A: (wrong) The embryo inherits half its chromosomes from its mother. the embryo inherits half its chromosomes from its mother a chemical change occurred Q: A student placed a small chip of limestone into a hydrochloric acid solution, and carbon dioxide gas was released. The carbon dioxide provided evidence that A: (right) a chemical change occurred. which can produce true hypotheses for incorrect answers and vice versa (see Figure 3). To evaluate the capacity for the system to find proofs for gold quality hypotheses, we run a proof search for all the hypotheses and intermediate inference nodes from the annotated trees in EntailmentBank. We measure NELLIE's proof recall with and without the time-intensive template-conditioned generation module. Table 2 shows the results, stratified by various categories of node. We find that the system without templates has higher proof recall on all and hypothesis nodes, which tracks with our results from the QA task. We note that this experiment does not consider the correctness of the generated proof itself, meaning that higher recall may simply reflect a tendency to find incorrect proofs for true statements. However, when we isolate only the 109 fully groundable hypotheses, we find that template-conditioned generation yields higher recall. It also provides incrementally higher recall of proofs for nodes whose gold decompositions are a pair of WorldTree fact leaves.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
We find that NELLIE can produce coherent and near-human-quality proofs of correct hypotheses; example proofs are shown in §D. However, the rel-atively low proof precision (.3 − .5) indicates that the system can often generate proofs for incorrect answers that bypass its various entailment filters. Given these incorrect proofs are fully interpretable, we have the opportunity to diagnose systematic error types that might be corrected for in future work. We enumerate a few such categories, examples of which are depicted in Figure 3.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
We find that the 2-premise RTE models have lower precision than desired, allowing for non-entailing h ⇐ f 1 , f 2 decompositions to be accepted and used in proofs. A common observed error pattern is assuming that taxonomic class members inherit all properties of their hypernyms, even if those properties are not universal of all members. A colloquial example is inferring penguins can fly from penguins are birds; birds can fly.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
We observe a nontrivial amount of semantic drift (Khashabi et al., 2019) between inference hops, culminating in RTE models failing to rule out non-entailments. For example, in block 2 of Fig 3, considering a saw requires light without the broader context of cutting wood leads to the model inferring the wrong meaning of saw. In the block's second example, which object loses temperature during heat transfer changes between hops.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
NELLIE's neural QA2D model is not immune from conversion errors when decoding a single hypothesis statement that represents a candidate answer to a multiple-choice question. Block 3 of Fig 3 depicts two common error cases: generating a true statement given an incorrect answer, and vice versa, generating a false or incoherent statement given a correct answer. Both cases often stem from information loss from the question context. The embryo inherits half its chromosomes from its mother is a true generic statement in isolation, but the question asked for a statement that explains a separate phenomenon. In the second case, the model generates a non-generic statement which shouldn't be provable using a factbase comprised of generics.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
We have crafted NELLIE specifically with intent to create systematic, interpretable, and granular reasoning behavior. This combined with our modularizing the generation and discrimination of candidates into separate decision points leads to our being able to diagnose a set of explicit, promising paths forward towards improving the system's reasoning capacity.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Better Entailment Filters This work has been concerned with mechanisms for improving the generative components of the hypothesis search: retrieval-and template-conditioned generation as a means to guide the search towards factbase-rooted proofs. These improvements will be better realized if the discriminative components of the system are less likely to accept improper entailment hops. As discussed in §7.3, NELLIE's proof precision is low, due in large part to incorrect entailment judgements. A perfectly-functioning entailment filter would serve a variety of benefits. It would not only raise precision, but also improve search efficiency, as much of NELLIE's budgeted search runtime is currently allocated to exploring the branches created by these incorrect judgments.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Reallocating this time to more promising, correct branches would improve proof recall.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Beyond using larger and stronger model architectures, improvements to the RTE classifiers might come from constructing domain-relevant training sets containing informative negative examples. Dalvi et al. (2022) suggest one form of this approach, having their inference model generate proofs of incorrect statements intentionally so that the resulting inference hops can be labelled for acceptability by workers. Another avenue for improvement might be through a version of dataset inoculation  or logic-guided data augmentation (Asai and Hajishirzi, 2020) stemming from the identification of improper reasoning patterns such as the property inheritance error described above. If these error patterns can be cheaply annotated or instantiated, we can train the classifiers to better identify when to filter them out. This could also be addressed using an inverse version of the approach by Bostrom et al. (2021) for annotating logical reasoning patterns using lexical patterns that imply specific logical operations.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Faster, Smarter Search Strategies The results reported in this work are the product of a straightforward depth-first proof search by NELLIE, making iterative calls to a neural sequence generation module that takes a couple seconds to run. This issue is exacerbated by the use of templateconditioned generation, which improves the quality of the search horizon, but at the cost of even greater generation times. Imposing a timeout of 90s does not give the system adequate time to explore its entire generated search horizon; we observe that it rarely recurs on more than one or two of the decomposition candidates at depth 1 of its search tree, as the majority of the search time occurs at greater depths. Future work should consider more informed ways to select candidates upon which to recur, so as to make better use of the time budget.
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
Better Declarativization Identifying a single generic hypothesis statement given a potentially multi-sentence question context and answer is a challenging task, and our neural seq2seq approach for QA2D conversion is far from perfect. As the entire inference procedure by NELLIE is predicated on the correctness of this decision point, it follows that performance on the fraction of the dataset for which the QA2D model errs would improve as the model improves. This conclusion is supported by the higher proof recall by NELLIE on the gold annotated hypotheses of EntailmentBank shown in §7.2, as it finds a proof for 10-15% more hypotheses than when using the QA2D model. Improvements to this model might come via annotation of supervised training data, using better decoding strategies than greedy decoding (chosen due to compute limitations) or using a stronger model than  Making More Questions Groundable Table 1 shows that NELLIE performs more effectively at QA on the subset of EntailmentBank for which there is a gold explanation tree fully grounded in WorldTree facts. This leads to the question: how to increase the coverage of the system's factbase so that more questions can be considered "groundable"? One approach might be to incorporate the facts of more knowledge stores such as Concept-Net (Speer et al., 2017), which contains many useful lexical and conceptual relations. Another could be to attempt to emulate the behavior by Entail-mentBank annotators of enumerating facts reflected in the question context itself (e.g. there is a stick).
Dynamic Generation of Interpretable Inference Rules in a Neuro-Symbolic Expert System
We have introduced NELLIE, a reimagined version of a classical expert system that relies on the inferential power of neural LLMs rather than handcrafted inference rules. The inference engine has the skeleton of a classical symbolic theorem prover, but the provided symbolic rules invoke neural predicates that allow for systematic reasoning over natural language statements. In order to dynamically generate inference rules, we introduce two mechanisms for knowledge-guided generation: conditioning on dense retrieval and inference-supporting fact templates. We find that even in the challenging scenario in which decisions must be fully grounded in a factbase-rooted proof tree, NELLIE performs competently on a pair of science QA dataset. Finally, we identified a number of promising avenues for future work that builds upon this paradigm, made tractable by NELLIE's modular approach to systematic neuro-symbolic reasoning. 
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Although pretrained language models (PTLMs) have shown remarkable question-answering (QA) performance, it is often unclear why their answers follow from what they know. While there has been substantial work on training models to also generate explanations for their answers (Wiegreffe and Marasović, 2021), or produce them via few-shot prompting, e.g., "chains of thought" , those explanations may not be faithful (the answer does not necessarily follow from them) and may not be truthful, in the sense that the language model itself does not believe 1 the explanation state- Figure 1: Given a question, Entailer searches for an answer hypothesis that is supported by an entailment proof. First it over-generates candidate proofs, then it removes those that the model itself does not "believe" (i.e., confirms via self-querying that it considers all the generated proof elements to be true). Finally it selects the best verified proof. Multistep proofs are generated by iteratively backward chaining on the premises (Section 3.2). ments that it generated. Rather, our goal is to generate answers that systematically follow from the model's own internal beliefs, materializing those beliefs as explicit statements that can then be inspected. Such a capability offers new opportunities for understanding, diagnosing, and ultimately correcting errors in a language model's behavior.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Our approach uses a combination of generation and verification, implemented in a system called Entailer 2 . Chains are constructed by backward chaining from candidate answers, recursively using a language model (LM) trained for a single backward-chaining step. For each step, Entailer over-generates candidate entailments, then filters out those that do not conform to its own internal knowledge ("beliefs") by self-querying, asking itself whether (a) the generated premises (leaves of the proof step) are true, and (b) each entailment step is valid (Figure 1). It then recursively backwardchains on premises until the overall proof confidence cannot be further improved (or a depth limit d is reached). Finally, the candidate answer supported by the highest-scoring chain of a reasoning is returned. As a result, the system has materialized some of its latent knowledge from which the selected answer follows. Most significantly, the resulting proof is thus both faithful (the answer follows from the proof) and truthful (the proof reflects the system's beliefs), providing a previously unavailable window into the model's beliefs about the world and their implications, e.g., Figure 2.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
To train the Entailer model, we use a combination of the existing EntailmentBank dataset (Dalvi et al., 2021), plus a new crowd-annotated dataset that we construct by bootstrapping (train an initial model, generate candidate entailment examples with it, then annotate those examples as extra training data). The model is then frozen, and Entailer is then applied zero-shot to new datasets, i.e., Entailer is a treated as a general-purpose, fixed model specialized for reasoning, rather than requiring finetuning for new tasks.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
We evaluate Entailer on two existing datasets, OBQA (Mihaylov et al., 2018) and QuaRTz (Tafjord et al., 2019). We find that its reasoningbased QA accuracy is similar to its direct QA accuracy, with the advantage that a supporting chain of reasoning is also produced. We also perform a human evaluation, and find that 70% of time users judge the chains to clearly show how an answer followed from their premises, substantially higher than for explanations produced by a comparable high-performance QA system, Macaw (Tafjord and Clark, 2021). Our contributions are thus:
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
1. In all these systems, the required facts were expected to be provided explicitly to the model. In contrast, Entailer's reasoning uses its own internal, latent knowledge, as well as (optionally) externally provided facts. LeapOfThought (Talmor et al., 2020) demonstrated that reasoning with a combination of implicit and explicit knowledge was possible for simple 1-step inferences. We expand this for multi-step inference, and (unlike LeapOfThought) have the system also explicitly articulate the implicit knowledge it uses, and its chain of reasoning.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Recent work has shown that generating a freeform explanation ("chain of thought") before an answer can also improve performance on a variety of tasks Cobbe et al., 2021;Nye et al., 2021). In these works, however, the explanations are unstructured, and there are no claims of faithfulness that the answer follows from the generation, nor that the explanations themselves represent model beliefs.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Pretrained LMs contain a vast amount of knowledge, and can be thought of as a kind of knowledge base to tap into (Petroni et al., 2019). Recent work has shown that this latent knowledge can be materialized as explicit English sentences or a knowledge graph using generative techniques, e.g., COMeT (Bosselut et al., 2019), ParaCOMET (Gabriel et al., 2021). Our work with Entailer similarly materializes its latent knowledge, but here in a goaldirected way, namely by producing a faithful chain of reasoning from facts it validates ("believes") as true to an answer. This articulation can be seen as a kind of self-talk, where a self-generated context can improve QA (Shwartz et al., 2020). However, here our generations are not used as context for opaque problem-solving, but are assembled into a well-defined chain of reasoning.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Beliefs: We refer to the model's factual opinions as "beliefs" rather than "knowledge" because those opinions may be wrong. In general, an agent can be said to believe p if it acts as if p was true (Schwitzgebel, 2019). Following (Kassner et al., Figure 3: An entailment tree is a set of multi-premise, 1-step entailments (red boxes) showing how the hypothesis (root node, green) is entailed from the leaf nodes (white). If all the leaf nodes are true, and all the 1-step entailment relations are valid, then we say the tree is a valid chain of reasoning for the hypothesis. 2021), we take a simple, syntactic operationalization of this, namely the agent answers "yes" to the question "p?", but also note that more semantic versions could be used, e.g., the agent also answers "yes" to paraphrases and implications of p. In general, models can sometimes be inconsistent in their beliefs (Elazar et al., 2021;Kassner and Schütze, 2020;Ribeiro et al., 2019). For our purposes here, we simply note that such inconsistencies may occasionally exist, and that techniques for inconsistency resolution could be applied in future to reduce these, e.g., (Kassner et al., 2021;Li et al., 2019).
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Like several previous systems (Section 2), Entailer treats reasoning as Natural Language Inference (NLI). In NLI, the basic unit of knowledge is (represented as) a sentence rather than a structure, and a proof 4 is a tree of multi-step, multi-premise entailments, e.g., Figures 2 and 3.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Within this framework, given a question, Entailer first generates candidate answers, then tries to prove each one, selecting the answer with the highest-scoring proof. We now describe these steps.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Given a question, Entailer first generates candidate answers and converts these into declarative hypotheses (e.g., "Is the sky (A) blue (B) yellow" → { H 1 = "The sky is blue.", H 2 = "The sky is yellow."). 5 An N -way multiple choice question yields N hypotheses. A true/false question yields  Table 1: Examples of the three input/output angles used by Entailer. The first generates a candidate entailment rule P H given H. The second and third score whether each premise, and the entailment itself, is valid, using tokens V/I in the input to indicate that S d /S e is the desired output. Figure 4: The entailment tree is grown recursively, the algorithm looking for the best tree (maximizes the overall score of the root node). Each node has a fixed, direct ("fast") score (in red), and (for internal nodes) a proof ("slow") score (in blue) computed from its children. The overall node score (highlighted) is the highest of the two. If expanding a node increases its overall score (e.g., step 3), that increase is propagated upwards and recursion continues. If expansions cannot improve a node's score further (e.g., steps 2 and 4), the expansions are pruned and that node becomes a leaf (red bars).
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
2 hypotheses. For open-ended questions, Entailer first collects N candidate answers generated by an external source (Macaw (Tafjord and Clark, 2021) using nucleus sampling (Holtzman et al., 2019)) then forms N hypotheses from them.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Step
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
The core of Entailer is generating and validating a single entailment step that entails a hypothesis. We define the following data types: H: A hypothesis (English statement) to prove. P: A set of premises {p 1 ,...,p i } (sentences) that together may entail the hypothesis H. Together, P and H form a one-deep entailment step, denoted by P H. Q: A question posed to Entailer. A: A candidate answer for consideration. C: An optional context (set of sentences) relevant to the problem. This allows Entailer to also use external knowledge, if available, when generating a tree. We train a model (details in Section 4) with the three input/output behaviors below (optional inputs shown in parentheses): (QAC)H → P : Given a hypothesis H, generate a set of premises P that may entail H (QAC)H → S d : Score whether the model be-lieves that a hypothesis H (or premise p i ) is true (S d > 0.5) or not, (i.e. perform yes/no QA). We call this the direct score (range 0-1). (QAC)P H → S e : Score whether the model believes a candidate entailment (P H) is valid (S e > 0.5) or not, i.e., P validly entails H (range 0-1).
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Examples of these three angles are in Table 1.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
To generate a single backward-chaining step we adopt an overgenerate-and-filter approach, also found useful elsewhere Cobbe et al., 2021;Li et al., 2022). First, given H, we use the angle H → P to generate a set of premises P that may entail H. We then check that the model believes all the premises p i ∈ P using the H(= p i ) → S d angle, and that it also believes the inference step P H itself is valid (independent of whether the p i are true or not) using the P H → S e angle. The proof score, denoting how well the 1step proof supports the hypothesis, is the product of the premises' and entailment scores:
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
We repeat this k times using nucleus sampling to obtain a diversity of alternative proof steps, and then select the highest-scoring one P H, as illustrated in Figure 1.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
This one-step backward chainer is embedded in a larger control algorithm that grows a multi-step entailment tree, searching for the best tree. This algorithm is illustrated in Figure 4 and described below. The full algorithm is in Appendix A.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Each node N in the tree has two associated scores, the direct ("fast") score s d , denoting the model's direct belief in N (in red in Figure 4), and (for internal nodes) the proof ("slow") score s r , denoting how confidently the model can prove N (in blue), computed from its children. The overall score s is the max of the two. The proof score s r is recursively defined as the product of its children's overall scores times the entailment score:
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
The algorithm starts with an initial hypothesis node H, then iteratively expands each leaf node N , looking for a proof that scores higher than the direct score s d of that node. In other words, can the system prove N with a more confidence than simply "guessing" if N is true? If it can, the node's overall score s (max of the two) will increase, that increase is be propagated up the tree, and the expansion is retained, e.g., step 3 in Figure 4. If expansions cannot improve a node's score further (e.g., steps 2 and 4), the expansions are pruned and that node becomes a leaf (red bars in Figure 4). Note that because premises are self-generated rather than externally provided, this stopping condition has a different semantics to earlier work, e.g., (Kalyanpur et al., 2020;Bostrom et al., 2021): Rather than stopping when externally known facts are reached, Entailer stops when strongly believed facts are reached, and more backward chaining can no longer improve a hypothesis' confidence.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
This whole procedure is repeated for each candidate answer hypothesis (Section 3.1). Finally the system selects the answer corresponding to the hypothesis with the top-scoring proof s(H).
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
The core of Entailer is the model for one-step inference (Section 3.2.1), with the three functionalities listed in Table 1. As Entailer is intended to be a general-purpose system, the model is trained onetime for these three functionalities, and then frozen. It is then applied zero-shot to new datasets, e.g., the evaluation in Section 5.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
To train Entailer's model, we leverage (the training partition of) the EntailmentBank dataset (Dalvi et al., 2021). EntailmentBank contains 1840 multiple-choice science questions (1313 in the training partition) along with their correct answer, a hypothesis expressing the question and answer in declarative form, and a multistep entailment tree expressing how the hypothesis follows from a set of facts drawn from a corpus of science facts (the WorldTree corpus (Xie et al., 2020)). Using the notation introduced earlier, each EntailmentBank example is of the form: 
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
EntailmentBank only contains positive examples of entailments. To obtain negative examples, we first ran an earlier, positive-only-trained version of Entailer to generate 1-step proofs of (hypotheses for) incorrect answer options in EntailmentBank's questions (4-way multiple choice), resulting in (necessarily bad) proofs for the three false hypotheses. (This was done using just the H→P angle, without verification). Note that Entailer will generate some kind of proof even for false hypotheses, e.g., A rabbit has six legs because: 1. A rabbit is an animal 2. Animals have six legs These invalid proofs will be incorrect either because a generated fact is false, and/or because the inference itself is not a valid entailment. To distinguish these, we use crowdworkers to assess whether the generated facts were true, and if the entailment itself was valid. The 1313 questions result in 3939 proofs for false hypotheses. Dropping the few with more than two premises (to simplify the crowdsourcing interface), crowdworkers annotated 3673 proofs, using labels T/F/? for each premise and T/F/? for the entailment itself. Each proof was annotated by 3 crowdworkers, then an additional 3 workers provided additional annotations for cases with no initial majority verdict. Dropping premises/entailments without a final majority verdict, we end up with 7013 additional labeled premises for the H → S d angle, and 3391 additional labeled entailments for the P H → S e angle.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
The crowdworker interface is in Appendix B.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
We also augment the training data with duplicate examples but with additional, optional input fields: QA: The input QA question/answer-option pair, as well as the hypothesis H C: A context consisting of up to 5 relevant sentences, allowing explicit external knowledge to be provided if available.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
To generate examples of C during training, we use a mixture of sentences drawn from (a) the gold (target) entailment (i.e., the gold premises), and (b) sentences retrieved from a corpus of similar-styled knowledge (namely all the leaf sentences used in the EntailmentBank entailment trees), mixed in different ratios so the model is exposed to a mixture of high and medium relevance sentences.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
In this work we do not use any context C at test time, but it is utilized in concurrent work for providing feedback to the overall system (Mishra et al., 2022).
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Further details of training are given in Appendix C1.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
We train a T5-11B multi-angle model, Entailer, following the multi-task setup similar to Macaw (Tafjord and Clark, 2021) for the three functionalities described in Table 1. 6 Details of hyperparameters and other settings are provided in Appendix C2.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Our goal is to generate answers supported by faithful, truthful chains of reasoning, without significantly impacting performance. Our two corresponding reserach questions are:
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
1. How does Entailer's proof-based answer accuracy compare with the direct QA accuracy (both zero-shot)? 2. How good are the generated entailment-based proofs? And are they better than those produced by a purely generative model? For the first question, we evaluate using two existing multiple-choice datasets, namely OBQA (Mihaylov et al., 2018) and QuaRTz (Tafjord et al., 2019). These datasets contain multiple-choice questions that (typically) require multihop reasoning, rather than being simple lookup questions. We 6 The scores use the token probability of generated "true" or "false" output text. For the second question, we collect human judgements of whether the hypothesis clearly follows from facts in the proof, and compare its proofs with explanations generated by a high-quality baseline model, Macaw (Tafjord and Clark, 2021).
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
We evaluate Entailer's proof-based QA accuracies under various conditions, and compare them against its direct QA accuracy: 1. Direct QA: Here we measure the model's ability to directly answer the test questions (zero shot) using the H → S d angle. One can think of this as the "fast thinking" answer. Note that this capability of the frozen model was trained on the same data as the rest of Entailer, so is a fair comparison. 2. Entailer: Here we measure Entailer's ability to answer the test questions (again zero shot) by generating, scoring, and comparing entailment proofs for each answer option. One can think of this as the "slow thinking" answer. We vary:
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
• maximum proof depth d = 1 (blue in Figure 5) or 3 (green) • degree of search: (a) greedy: use the first (k = 1) generated entailment at each step, or (b) sampled top level: pick the best of k = 6 entailments for expanding the root hypothesis node. (≈ six times more computationally expensive than (a)).
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Note that these proofs are are faithful explanations of why an answer was chosen, as the selected answer by definition is always the one with the highest-scoring proof.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
3. Entailer + Direct: Here we combine the two by selecting the overall most confident answer of Direct and Entailer (using c d (H) or c r (H), Appendix A). Here, the proofs are not always faithful explanations of an answer, as the chosen answer may not be the one with the highest-scoring proof.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
The results are shown in Figure 5, and suggest that: Proof Scores are competitive with direct answer scores. In Entailer's best configuration (sampled top-level k = 6, max depth d = 3, last bar), its reason-based answers have an accuracy of 75.2/75.4 for OBQA/QuaRTz respectively, not significantly different to the Direct scores of 75.2/74.1. This is important, as it suggests there is no significant accuracy penalty for proof-based answers. Sampling proofs helps: Using sampling for the top-level proofs (last 4 bars) always outperforms greedy proof selection by a small amount. Allowing deeper proofs does not significantly affect accuracy: Although deeper proofs 8 slightly help in the combination of Entailer+Direct, and may provide more information to a user, the accuracy differences are not significant. When Entailer + Direct are combined, by selecting the most confident answer (last two columns), we lose the guarantee of faithfulness, as the selected answer may not be the one with the highestscoring proof. In practice, this occurs for 16.8% of the questions (OBQA), 14.2% (QuaRTz). In addition, we find this combination does not have significant performance gains, so has no obvious advantage in these experiments.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Note that we are measuring zero-shot performance on our test datasets, so our results are not comparable with leaderboard entries. 9 More im-8 The distribution of proofs with different depths 1, 2, and 3 was 162, 232, and 106 respectively for OBQA, and 123, 256, and 178 respectively for QuaRTz. 9 For a comparable datapoint on OBQA, (Brown et al., 2020) report zero-shot GPT3 scores of 57.6% and few-shot 65.4% on OBQA, so Entailer's ∼75% scores are a strong zero-shot baseline for an 11B model. More recent work us-portantly, though, our goal is not a state-of-the-art zero-shot model, but rather a model that can show how answers systematically follow from its own internal beliefs. Our results suggest this is possible with high reliability, and, as an additional bonus, without loss of zero-shot accuracy. Thus, rather than just answers, we now get answers supported by faithful chains of reasoning.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
For our second question of evaluating the quality of Entailer's proofs, we compare against explanations generated by Macaw, 10 a public, state-of-the-art QA system with explanation capability (Tafjord and Clark, 2021). Examples of explanations from both systems are in Appendix D. Six annotators compared 1-deep Entailer proofs with explanations from Macaw, scoring each along four dimensions, and then comparing the two:
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
1. Does the conclusion clearly follow from the premises? 2. Are all the premises correct? 3. Are all of the premises relevant? 4. Does the explanation introduce something new and useful, i.e., does more than just restate the conclusion in different words? 5. Which explanation do you prefer? Answer options for questions 1-4 were yes/somewhat/no, and for question 5 were first/similar/second. The ordering of explanations were scrambled so the annotators did not know which explanation was which, and in fact they were unaware that the different explanations had been generated by different systems. We collected annotations for 100 pairs of explanations for correct answers to 100 OBQA dev questions. The annotators were recruited from our institute, spanning a broad range of age (20-60) and experience.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
The results ( Figure 6) suggest several findings: 1. In absolute terms, Entailer's conclusions were ing rationale-augmented prompt ensembling with much larger models  has reached few-shot (with rationales) scores of 91.0% (PaLM-540B) and 88.4% (GPT3-175B) on OBQA.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
10 Note that comparing with a baseline explanation generator trained on our data, i.e., just using H → P angle without verification, would not be informative, as such explanations would necessarily be worse: By definition, the verifiers remove explanations with either (believed to be) false premises and/or bad inferences, hence removing the verifiers will increase the frequency of false premises and bad inferences (confirmed through sample analysis). Hence we instead use a strong, external system as a comparative reference point. Figure 6: Users' assessments of Entailer's proofs (red), compared to Macaw's explanations (blue), showing percent of times annotators answered "Yes". Entailer's conclusions were judged to "clearly follow from the premises" in over 70% of the proofs (first bar), substantially more than Macaw's explanations (34%). judged to clearly follow from the premises in the large majority (over 70%) of the explanations, and substantially more than Macaw's explanations (34%). This potentially contributes to system trustworthiness, where understanding how evidence supports a conclusion is critical. 2. ≈90% of Entailer's self-verified premises were judged correct by users. Of the remainder, virtually all were labeled "unsure" (only 1 Entailer fact was labeled not correct), indicating that the there are few false beliefs in proofs for correct answers. Rather, vague facts (e.g., "Claws are used for cracking open shells") make up the remainder. 3. Entailer's explanations were clearly preferred (57% to 23%, last bar) over Macaw's. In particular, Entailer's arrangement of facts into a tree discourages irrelevant information (bar #3). Finally we note Entailer's proofs are faithful (showing how an answer was derived) and truthful (reflecting the system's own beliefs), while Macaw's explanations are post-hoc generated text. These all suggest the value of entailment trees as trustable explanations of a system's behavior.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
If Entailer answers a question incorrectly, either a model belief (belief error) and/or the reasoning itself (reasoning error) must necessarily be incorrect, unless the question itself is malformed (dataset error). To better understand these, we classified the 51/500 cases in OBQA where Entailer selected the wrong answer while the Direct answer was correct, and found: 1. belief errors (33%), where an incorrect belief led to a wrong answer, for example:
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
In a desert... plants grow closer together because 1. A desert...contains a low amount of water. 2. As the amount of water decreases, plants are forced to grow closer together to conserve water.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Note that here the reasoning is correct but the second is premise is false. 2. dataset errors (20%). In several cases, the question was ambiguous (e.g., does "animal" include humans?) or more than one answer option was valid (OBQA is a crowdsourced dataset). 3. reasoning errors (47%): 3a. Near-tautologies (20%): of the form "X because 1. X , 2. ...", where X is a near-repeat of the hypothesis. In such cases, the proof offers little new information.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Basic reasoning errors (10%):, e.g., During ...fall, new leaves begin to grow because 1. During fall, old leaves begin to fall. 2. New leaves begin to grow.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Here entailment is simply invalid.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
3c. Incorrect abductive inferences (9%): of the form A because (A → B) and B. While sometimes useful, these inferences are not sound and can produce incorrect conclusions, e.g.,
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Cooking food requires a fire to be built because 1. Cooking food requires heating the food. 2. Fire can be used to heat things.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Quantification and exceptions (8%): where both beliefs and reasoning seem reasonable, but the specific case does not hold, e.g., Seeds are often found inside a strawberry because 1. Seeds are often found inside fruits. 2. A strawberry is a kind of fruit.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
At its best, Entailer decomposes an uncertain hypothesis H into premises P which it is very confident about. For example, Entailer is unsure whether A suit of armor conducts electricity, but it confidently believes the generated premises:
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
A suit of armor conducts electricty because 1. A suit of armor is made of metal 2. Metals conduct electricity Thus an uncertain conclusion is replaced by more certain premises, and we see Entailer performing particularly well for such questions. However, there are questions that are largely "fact lookup", where a proof may be less helpful. For example, the model is already very confident about the hypothesis Jupiter is the largest planet in the Solar System; decomposing this into 1. The largest planet has the greatest mass plus 2. Jupiter has the greatest mass in the solar system has not obviously made answering easier. In fact, Entailer's algorithm is specifically designed to account for this, only growing a proof when the confidence in the premises improves the confidence in H, thus tailoring its degree of reasoning to the complexity of the problem at hand.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
If a system can show how its answers systematically follows from its own beliefs, articulating those beliefs in the process, then this opens a window into the model's internal state for the user. As a result, new opportunities arise for identifying and correcting the model's misunderstandings, so the system gradually improves over time (sometimes referred to as explanatory interactive machine learning (XIL) (Teso and Kersting, 2019)). One vehicle for doing this is to use Entailer's (currently unused) context field C at runtime: If the user asks a question, receives a wrong answer, and sees an incorrect belief in the proof, they would provide the corrected belief, then re-ask the question with the corrected belief in the context. This encourages the model to use the corrected belief in its new answer and proof, rather than just repeat the same bad belief. Such overrides would then be stored and retrieved from a persistent memory to use for future questions also. A simple, hypothetical dialog illustrating this is shown in Figure 8. This is an exciting avenue made possible by this work, currently used by the TeachMe system (Mishra et al., 2022).
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Our goal is a system that can show how its answers systematically follow from its own internal U: Can a magnet attract a penny?
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Entailer tries to prove H (A magnet attracts a penny) and the negation neg(H), and reports the best proof E: A magnet can attract a penny because:
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
1. A penny is made of copper 2. Copper is magnetic Do you agree?
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Here Entailer gives the wrong answer, arising from an incorrect belief #2. The user offers a correction: U: No. Copper is not magnetic System tries again, trying to prove H and neg(H) with context C = "Copper is not magnetic". C biases the model away from its prior mistake, effectively changing the model's belief. The new best proof is reported. E: A magnet cannot attract a penny because:
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
1. A penny is made of copper. 2. Copper is not magnetic Do you agree?
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
The system now gets the right answer, having learned that copper is not magnetic from the user. C is added to memory for use in future questions, via information retrieva. U: Yes Figure 8: A hypothetical dialog illustrating how a user (U) might identify and correct Entailer's (E) incorrect beliefs through interaction. Here Entailer initially gets the wrong answer due to an incorrect model belief ("Copper is magnetic"). The user offers a correction, which is then provided as context when re-asking the question, effectively overriding the prior bad belief (the user has "taught" the model). By storing such corrections in a memory, such belief updates persist over time.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
beliefs, and materialize those beliefs in the process. Entailer is, to our knowledge, the first system to demonstrate this capability, achieved using an "over-generate and verify" approach for each backward-chaining step. Our evaluation suggests that Entailer's proof-based answer accuracy is similar to the "direct" QA accuracy, with the additional benefit of providing a faithful, truthful chain of reasoning showing how its answers follow from its internal beliefs. The significance of this is that these chains provide a window into the model's internal beliefs and their relationships, allowing users to both verify a system's answer, or if the system provides an incorrect answer, to identify the incorrect belief leading to that error. This in turn offers new opportunities for a user to correct the system's misunderstanding by overriding a faulty belief, e.g., by adding a memory of user corrections/overrides (Tandon et al., 2022), or by editing the model parameters directly (Mitchell et al., 2021), a step towards interactive systems that can both explain to, and learn from, users over time (Mishra et al., 2022). Entailer data and models are available at https://allenai.org/data/entailer. We look forward to future developments in these directions.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
We have shown how a neural system can expose how its answers systematically follow from its own internal beliefs, providing a window into the model's system of beliefs. While exciting, there are several limitations with the current work and opportunities for the future. First, the system is not perfect at generating coherent chains of reasoning, sometimes producing entailments that are invalid or nearly tautologous (Section 5.4.1 and Figure 7). Improved proof generation and scoring techniques would help address this.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Second, like others, we use textual entailment as the basic reasoning operation, but the definition of entailment remains somewhat imprecise (a valid entailment is one that "a person would typically infer." (Dagan et al., 2013)), contributing to noise in the model's training data. A more precise characterization of reasoning validity would help in both generation and evaluation of reasoning chains.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Third, we assume the model is generally consistent about its beliefs, but in some cases the model may verify contradictory statements, making it less clear what the model actually believes in such cases. We currently do not handle such situations. Use of a global notion of belief (rather than per question) would be a valuable avenue to explore, e.g., (Kassner et al., 2021).
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Fourth, as a practical matter, recursive construction of proofs is computationally expensive (≈360 seconds/question for up to depth-3 proofs for 4-way multiple-choice, Appendix A.2). Improvements to the search algorithm would allow faster experimentation, and also help deploy the model in a practical setting.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Finally, we have speculated that showing users faithful, truthful chains of reasoning might be a basis for a conversational system, where users could correct and teach the system in cases where it was wrong. However, this is currently just a conjecturefutures explorations into how this might be realized would be valuable.
Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning
Like any other large-scale language model, despite the best intentions, there is a risk of our model producing biased or offensive statements as part of its explanations. We release our models for research purposes only.
Faithful Reasoning Using Large Language Models
Among the many tasks that contemporary large language models (LMs) can perform (Alayrac et al., 2022;Nakano et al., 2021;Zeng et al., 2022), question-answering is potentially one of the most useful (Rae et al., 2021). However, the proficiency of these models typically goes hand-inhand with an unacceptable level of opacity. The assumptions behind an answer and the intermediate steps of reasoning that justify it -insofar as these exist -are hidden from the user. This prevents the user from verifying an answer, makes it difficult to debug a model when it gets an answer wrong, and undermines overall trust in the model's responses.
Faithful Reasoning Using Large Language Models
By contrast, a system that reasons faithfully is one whose underlying computations mirror standard definitions of logical validity. Such a system can supply the user with an interpretable reasoning trace, which allows them to understand how the model reached its final answer. Exposing a model's assumptions and reasoning steps ( Figure  1) in this way enables the user to spot mistakes the model may have made, and empowers them to decide for themselves whether the model's conclusions are justified. This provision is especially important given that LMs are trained on human data collected from the internet, which makes them vulnerable to picking up and perpetuating bias (Bender et al., 2021;Betz et al., 2021;Weidinger et al., 2021). Presented with a context of relevant knowledge and a question, an LM may base its answer on information encoded in its weights rather than prioritising the information present in the context (Dasgupta et al., 2022). Without an interpretable reasoning trace, we cannot know how a model has reached its answer. Did the model rely on its priors, which may be biased, or did it obtain an answer by reasoning correctly with relevant knowledge?
Faithful Reasoning Using Large Language Models
In this paper we develop a forward-chaining model that reasons faithfully in the sense defined above (and more formally in Section 2). The backbone of our system, denoted SI, comprises two fine-tuned LMs, one for selection and one for inference. The interleaved operation of these two components has a causal structure ( Figure  2) that mirrors the definition of logical validity. This guarantees that the model's answers follow logically from the given context under certain assumptions.
Faithful Reasoning Using Large Language Models
Two further fine-tuned language models complete our architecture. First, the halter is used to terminate the reasoning process and return an answer in the required format. If the trace does not terminate within a specified number of steps then the answer is considered to be 'Unknown', allowing us to filter model answers and increase answer precision. Second, a learned value function, which assesses the quality of the current reasoning step is deployed to guide a beam search over reasoning traces to enhance their quality and further boost overall performance. We evaluate our model on two datasets, Proof Writer (Tafjord et al., 2021) and a questionanswering version of EntailmentBank (Dalvi et al., 2021). We shown that our model outperforms baseline models on final answer accuracy and that our proposed halter and search methods also lead to compounding boosts in performance (Tables 2 and 1). We show that in most cases SI produces higher quality reasoning traces than baseline models (Figures 9 and 8). It is less likely to "hallucinate" facts (Table 5), is better able to utilise the context (Table 3) and is more likely to use its trace to answer questions (Table 4). Finally, our model can accurately predict when it knows the answer ( Figure 6).
Faithful Reasoning Using Large Language Models
In this Section, we formally define the concept of valid forward reasoning in the context of our framework, adhering closely to textbook definitions from formal logic (e.g. Hamilton (1988)).
Faithful Reasoning Using Large Language Models
Definition 3. A reasoning trace C, T , where T = 0 , 0 , 1 , 1 , . . . , , is connected iff for every reasoning step , , for every statement in the set either ∈ C or = for some < .
Faithful Reasoning Using Large Language Models
A reasoning trace C, T , where T = 0 , 1 , . . . , , is valid if it is connected and each reasoning step = , is correct (in the sense that logically follows from ).
Faithful Reasoning Using Large Language Models
In the next section, we introduce the components of our architecture and show how it satisfies the requirements of faithful reasoning, under certain assumptions.
Faithful Reasoning Using Large Language Models
We begin by introducing Selection-Inference (SI), the step-wise forward reasoning backbone whose causal structure (see Figure 2) satisfies the requirements for producing valid reasoning traces. We then describe a component for halting, which  looks at the output of a Selection-Inference step and determines if there is sufficient information to answer the question. When there is sufficient information, the model predicts the answer in such a way that it cannot rely on knowledge embedded in its weights, but must depend on the reasoning trace. Finally, we introduce a value function, which is used to perform a step-level beam search on the reasoning traces to find the best candidate for answering the question. A schematic of our model is shown in Figure 3. We now describe each of these components in more detail. Note that (in contrast to Dalvi et al. (2021)) each component in our model is trained in isolation, and at no point do we optimise our pipeline for final answer accuracy.
Faithful Reasoning Using Large Language Models
Given a question and a context consisting of a number of statements sufficient to answer the question, we would like our model to produce a sequence of deductive reasoning steps that answers the question (Figure 1). To achieve this, the SI backbone splits each reasoning step in two (Defn. 1). First, given the question, the Selection model chooses a set of statements from the context (the selection). Second, the Inference model predicts an entailment by computing a statement that follows from the selection (the inference).
Faithful Reasoning Using Large Language Models
The inference is then added to the context, and that concludes a single step of reasoning. Multiple iterations of SI are carried out to produce a reasoning trace (Defn. 2). The final inference is used to answer the question.
Faithful Reasoning Using Large Language Models
To ensure that the reasoning trace is connected (Defn. 3), the Selection model is obliged to select elements only from the context, and is unable to 'hallucinate' facts. Similar to Tafjord et al. (2021) and Dalvi et al. (2021), we achieve this by training an LM to refer to statements in the context by their sentence labels, for example, 'sent 3'. These are used to compose sentences of the form "X. We know that Y and ... and Z.", where X, Y, and Z are sentence labels (Figure 4). These sentences are passed directly to the inference model. Figure 4 | The Selection model. The role of the Selection model is to take the context and question and select a number of statements from the context to feed to the inference model. It is crucial that the Selection model is not able to 'hallucinate' facts. To achieve this we fine-tune a LM to predict sentence labels, as show in (i). We then extract the only the sentence labels (ii) and compose a sentence (iii). The statements from the context are then substituted back in (iv) resulting in a sentence composed of statements from the context.
Faithful Reasoning Using Large Language Models
To encourage it to produce correct reasoning steps, the Inference model is trained to predict an entailment given only the selection. By not allowing the Inference model access to the question, we prevent it from "cheating" (directly predicting the answer from the question). While we cannot guarantee that every reasoning step is correct, in the sense that the inference logically follows from the selection (Defn. 4), our implementation makes this more likely. Under the assumption that the Inference model produces logically correct inferences, our model is guaranteed to produce valid reasoning traces.
Faithful Reasoning Using Large Language Models
SI allows us to produce multi-step reasoning traces, but it does not tell us when to stop the reasoning process. Furthermore, while we may want to use the final inference as the answer, it may not be in a desirable format. For example, if we are asked whether a statement ' ( )' is true or false, our final inference my be ' ( )' or ' ( )' where is a predicate and a constant. Alternatively, we may want to answer multiple-choice questions, which require one answer to be output from a given set of possibilities.
Faithful Reasoning Using Large Language Models
In light of this, we deploy a two-stage Halter ( Figure 5), which uses an LM fine-tuned to predict whether the question can be answered given the current inference and the question. If the question cannot be answered, 'Unknown' is returned. Otherwise, the Halter computes an answer, using the same LM, given the final inference and minimal additional information. It is important that the model is obliged to use the final inference, rather than depend on knowledge embed-ded in its weights. For example, if we are answering a multiple-choice question, we may provide the choices alongside the final inference, and use the model to output the choice that most closely matches that inference.
Faithful Reasoning Using Large Language Models
To determine if the system is ready to answer the question, we provide the Halter with a sentence of the following form: 'Question:{question} Given {inference}. Do you know the answer?'. The output of the Halter LM is then either ' Yes' or 'No'. If the output is 'Yes', the Halter LM is then prompted again to answer the question with a prompt of the following form: 'Given {infer-ence}. Which of the following most closely matches: {choices}? Answer:'. The output is one of the choices.
Faithful Reasoning Using Large Language Models
The Halter is applied after each step of SI to the resulting inference. If the output of the Halter is 'Unknown' then we proceed to another iteration of SI. If the output of the Halter is an answer, then the process is terminated and the answer is returned. If, after a pre-specified number of SI iterations, the system has not halted, it returns the answer 'Unknown' (Alg. 2). An additional benefit of this is that it allows the model to say that it cannot answer the question, rather than making up an answer. We see a notable increase in performance when we remove questions that the model "thinks" it cannot answer ( Figure 6). This has significant implications for trust, safety and the deployment of systems in the real world, where precision (rather than recall) is a priority.
Faithful Reasoning Using Large Language Models
The selection module is non-deterministic, in the sense that it samples from multiple candidate statements, and this induces a tree of potential reasoning traces. We use beam search to explore this tree in order to find high quality traces. To enable this, we introduce a value function which computes the value of adding a reasoning step to the current trace. The value function is a language model, LM value , fine-tuned on examples of partial reasoning traces that culminate in a "correct" or "incorrect" next step. A step is considered "correct" if it is both logically valid and is on the ground truth (shortest) reasoning path. A step is otherwise considered "incorrect".
Faithful Reasoning Using Large Language Models
Assuming that the sum of probabilities for "correct" and "incorrect" is close to one, we can use log value ("correct"|reasoning trace) to score reasoning traces as they are being constructed, where value denotes the distribution over tokens learned by the language model, LM value .
Faithful Reasoning Using Large Language Models
We use the value function to guide a beam search. Starting from a single empty trace we use SI to produce candidate steps. We evaluate each of these steps using the value function and keep the top <= . We use SI again to generate candidate next steps for each of the traces, resulting in × traces. These are evaluated using the value function and the best traces are kept. We continue this process until all the traces have halted.  First the model determines if a question is answerable given the current inference. If it is, the model combines minimal additional information (that could not be used on its own to answer the question) and predicts the answer.
Faithful Reasoning Using Large Language Models
from WorldTreeV2 (Xie et al., 2020) needed to answer the question, and Task 2 that additionally includes distractors. EntailmentBank is not a QA dataset, rather the task requires predicting the entailment tree given the hypothesis and context. We reformulate the EntailmentBank dataset (taking additional information from the original ARC tasks) into an EntailmentBankQA (EB) dataset by creating a dataset of context, question, choices, answer and a proof derived from the entailment tree. Our task is to predict the answer and proof given the question, context and choices. This task is more similar to the ARC task, however, here we provide the context and predict a reasoning trace that leads to the answer.
Faithful Reasoning Using Large Language Models
The selection model is trained on individual steps of reasoning; given the context and any previous inferences the model is trained to predict the sentence labels which refer to statements in the context. The inference model is trained to predict an entailment given a number of statements from the context. Each reasoning step in each training example in the original dataset produces one training data point for selection and one training point for inference. Examples of input, target pairs used to train the LMs are shown in Figures  11 and 12. By training the model to select statements by labels we prevent the model from being able to make up facts that are not present in the context (Tables 6 and Table 5). Tables 7 and 8 show the inference accuracy on the test set.
Faithful Reasoning Using Large Language Models
We use the ground truth reasoning traces from each dataset to produce training examples for the Halter LM. The halter has two functions, (1) learn when there is sufficient information to answer the question given the current inference (and the question) and
Faithful Reasoning Using Large Language Models
(2) answer the question given the current inference and the choices. An example of how data is generated is shown in Figure  13. To evaluate each halter independently of the Proof Only baseline or SI model, it is applied it to the ground truth proofs from the test split .  Tables 1 and 2 show results for PW and EB respectively. We see that the PW halter performs almost perfectly while the EB halter achieves 88.8% accuracy.
Faithful Reasoning Using Large Language Models
The Halter endows our model with the desirable property of predicting when it does not know the answer. Figure 6 shows that our halter model can reliably predict when the answer is known. When we filter out the problems where the model does not know the answer, we obtain nearly perfect accuracy on the PW dataset for all depths and 87.5% & 83.7% accuracy on Task 1 and 2 of EB dataset respectively. This has significant implications for the deployment of such models in scenarios where precision matters.
Faithful Reasoning Using Large Language Models
The Value LM is trained to predict whether the current step of a reasoning trace is ' correct' or ' incorrect' 
Faithful Reasoning Using Large Language Models
We present results on both Proof Writer (PW) (Tafjord et al., 2021) and EntailmentBankQA (EB). We show that our model achieves 88.1% and 78.1% final answer accuracy on PW and EB respectively significantly outperforming baseline models (Table 1 and 2). We also perform an ablation to demonstrate the key role of search in our model (Table 1 and 2). Compared to baseline models, we show that our model often has higher reasoning trace accuracy; this is most evident on the more challenging tasks, for example PW depth-5 and EB Task 2 (Figure 8 and 9). Finally, we evaluate reasoning trace validity (Section 5.4) showing that baseline model are less likely to leverage the context when answering questions (Table 4 and 3) and are more likely to "hallucinate" statements than SI (Table 6 and 5). All results in this paper were obtained using 7B parameter Chinchilla language model models (Hoffmann et al., 2022).
Faithful Reasoning Using Large Language Models
We consider three baseline models. A Proof + Answer baseline where the LM is trained to predict the whole proof followed by the answer. A Proof Only baseline where the model is trained to predict only the proof. We use the Proof Only baseline to ablate the SI model by pairing it with our halter and search methods (see Tables 2 and  1). Finally, we include EntailmentWriter + Answer. This is the entailment model of Dalvi et al. (2021), which is fine-tuned to predict an entailment tree alone, extended for question-answering by training the model to predict the answer after the final conclusion.
Faithful Reasoning Using Large Language Models
While EntailmentWriter + Answer and Proof + Answer tend to be very good at predicting the intermediate inferences ( See Figures 17a and 9b) they tend to be less good at selecting the correct statements (see Figures 8a and 9a) and overall they perform less well on final answer accuracy (see Table 1 and 2). This suggests that the models are predicting the correct intermediate outputs, without selecting the correct supporting statements and that the models are unable to use the reasoning trace to answer the question. We also see that baseline models, with the exception of En-tailmentWriter, often make-up facts when reasoning (see Table 5), suggesting that their traces are not connected and therefore are not valid (Defn. 3). Finally, baseline models leverage information Figure 6 | Our model accurately predicts when it 'knows' the answer. The 'known only' accuracy is computed after filtering out the answers that are 'Unknown'. The 'all' accuracy is computed on all problems. This property is beneficial for applications that require high precision.
Faithful Reasoning Using Large Language Models
Figure 7 | The value function. Given the context, question and a partial reasoning trace the model predicts the log probability that the current step is correct.
Faithful Reasoning Using Large Language Models
in the context less well than our model, see Table 3, and Table 4 suggests that on Proof Writer, SI is the only model to consistently leverage the reasoning trace to answer questions.
Faithful Reasoning Using Large Language Models
On inspection of EntailmentWriter (Dalvi et al., 2021) outputs on the Proof Writer dataset we see that the model often 'cheats', where the final inference helps to answer the question, but does not follow from the previously selected statements. See Section E.1. Our inference model does not have access to the question and therefore does not have the ability to cheat in this way.
Faithful Reasoning Using Large Language Models
Tables 1 and 2 show final answer accuracy on the Proof Writer (PW) and EntailmentBankQA (EB) datasets respectively. Each table shows a comparison to baselines as well as an ablation; comparing both SI + Halter and the Proof Only + Halter baseline model with and without search. We see that SI outperforms EntailmentWriter + Answer and Proof + Answer baseline models on all PW and EB tasks. We also show that search improves both baseline and SI performance, providing the most significant improvement for problems that require more reasoning steps (PW, depth-5) and on problems with distractors in the context (EB, Task 2) On the EB dataset we see that SI model + Halter + Search yields similar performance to Proof Only + Halter + Search while also providing faithful reasoning traces, which the Proof Only models do not. In fact, Table 5 shows that the Proof Only models are prone to hallucinating facts in up to 40% of problems, while SI has made up facts to only 1% of problems 2 . In the next section we look at reasoning trace accuracy. 
Faithful Reasoning Using Large Language Models
Here we evaluate the reasoning trace accuracy of each model on the PW and EB datasets, see Evaluating reasoning trace accuracy on PW is straightforward since we are able to use exact string match to check whether two strings are the same. We show the Jaccard similarity between predicted and ground truth leaves (i.e the selection, Figure 8a), intermediate outputs (i.e. the inferences, Figure 17a) and steps (i.e. selection and inference, Figure 8b). Results show that SI had the highest Jaccard similarity for leaves and full traces while Proof + Answer and Entailment Writer + Answer have highest Jaccard similarity for intermediate outputs 17a. This sug-gests that these models are correctly predicting the intermediate outputs, but not via the correct reasoning. Note that this evaluation does not consider the ordering of the proof steps which may be inflating the perceived performance of the baseline models since the baseline models are able to cheat by predicting later reasoning steps without computing earlier reasoning steps.
Faithful Reasoning Using Large Language Models
Overall, on the EB dataset, we see that SI outperforms EntailmentWriter + Answer and Proof + Answer baselines on the more challenging task, Task 2, which has distractors in the context. Figure 9 shows the Jaccard similarity between predicted and ground-truth leaves (i.e. the selection) and the as well as the rouge scores between predicted and target intermediate outputs on the EB dataset (additional results in Figure  18).
Faithful Reasoning Using Large Language Models
Note that high baseline performance on the intermediate outputs (Figures 17 and 9) also suggests that the baseline models have been trained well and means that their poor final answer accuracy cannot be attributed to poor training but rather to the baseline models' inability to use the reasoning trace to answer the question.
Faithful Reasoning Using Large Language Models
While requirements for Defn. 1-3 are satisfied by the causal structure of our underling model (Figure 2). Requirements of correctness, for Defn. 4, (a) Jaccard similarity between the predicted and ground-truth selection, referred to as leaves, used to reason. We see that the SI models perform better than Baseline models.
Faithful Reasoning Using Large Language Models
(b) Jaccard similarity between the predicted and ground-truth reasoning steps. We see that the SI models perform better than Baseline models on the more challenging Task 2.
Faithful Reasoning Using Large Language Models
Figure 8 | Evaluating proof steps for Proof Writer. We compute the above values only on problems where the model predicts that the answer is not "Unknown". Additional analysis in Figure 17.
Faithful Reasoning Using Large Language Models
are less strongly enforced. Never the less we show bellow that, unlike baseline models, our model is not able to cheat and therefore, the correctness assumption is more likely to hold. First, however, we demonstrate that while SI satisfies the requirement of being connected, other baseline models fail to do so.
Faithful Reasoning Using Large Language Models
For a reasoning trace to be connected it must not hallucinate facts (Defn. 3). Tables 5 and 6 show that while some baseline models fail to satisfy this requirement and often hallucinate facts. For example, the Proof + Answer baseline makes up facts to solve 60% of EntailmentBankQA problems. On the other hand, SI makes up facts < 1% of the time, suggesting that >99% of traces produced by SI are connected reasoning traces.
Faithful Reasoning Using Large Language Models
Following Defn. 4 for a trace to be valid it must be connected (as above) and the steps must be correct; the inference must follow from the selection. Tables 7 shows that when fed with a valid selection the inference model reliably produces the correct inference. It is harder to evaluate inference accuracy on EntailmentBankQA, however Table 8 suggests that the inference model is accurate, with a RougeL score if 0.69.
Faithful Reasoning Using Large Language Models
Unlike baseline models, SI's causal structure (see Figure 2) forces it to use the reasoning trace to answer the question. On the other hand, some baseline models are able to 'cheat', answering questions without reasoning properly over the context. In other words, they depend more on the knowledge embedded in their weights than on the context provided and the reasoning trace constructed. To investigate this, we evaluate performance of a model that is given an incorrect context (a context different from the one needed to solve the problem) and compare this to performance when the model is given the correct context. If a model's answer depends on careful reasoning over the context, then it should be unable to answer the question when provided with a random context.
Faithful Reasoning Using Large Language Models
On the EntailmentBankQA dataset, we use a random context sampled from another problem in the dataset. Table 3 shows that both the Proof + Answer and EntailmentWriter + Answer models are still able to answer 30% and 23% of questions respectively, while SI + Halter is only able to answer 9%. We also see that while almost half of the final accuracy could be accounted for by 'cheating' or chance in the baseline models, less that 12.5% of SI + Halter final accuracy could be attributed to 'cheating' or chance.
Faithful Reasoning Using Large Language Models
On the Proof Writer dataset, we use an incomplete context which consists only of the rules needed to solve the problems but not the facts, making it impossible to construct the correct a valid trace to solve the problem. Table 4 shows model performance and the difference in performance, Δ, between models that use the complete and incomplete context. The Δ results suggest that SI + Halter is the only model that reliably makes use of the reasoning trace, while the other models rely on taking short cuts. For example, Proof + Answer may be taking short cuts, by looking for rules whose head predicate matches the predicate in the question.  Table 3 | EntailmentBank: Relative performance increase, Δ, when using the correct context as opposed to a random one. We expect models that actively make use of the context to have poor performance when using the random context and a larger performance increases, Δ, when using the correct context compare to when using the incorrect one. (*EW=EntailmentWriter (Dalvi et al., 2021))
Faithful Reasoning Using Large Language Models
Recent work on applying language models to reasoning problems has largely concentrated on improving final answer accuracy rather than producing valid, human interpretable reasoning traces that lead to the answers. For example, various methods of prompting (Wei et al., 2022) and iterative fine-tuning (Zelikman et al., 2022) have been used to encourage models to produce reasoning traces, and while this has led to improvement of final answer accuracy these traces do not support our understanding of how the answer was reached. Kojima et al. (2022) split the reasoning in two parts, first producing a reasoning trace and then predicting the answer given the question and the reason. Similar to our own model Zhou et al.
Faithful Reasoning Using Large Language Models
(2022) go one-step further and split each reasoning step in two: first asking an intermediate question and second, answering that question. While the authors suggest that their approach promotes compositional generalisation, unlike our (a) Jaccard similarity between the ground truth leaves (e.g. selection) and those used by the model. We see that SI outperforms all of the baseline models on the more challenging task, Task 2.
Faithful Reasoning Using Large Language Models
(b) Rouge score on the intermediate outputs (or inferences) from each step (ignoring order). The baseline models that do not use search or the halter perform poorly on Task 2. Figure 9 | Evaluating reasoning steps for EntailmentBankQA. We compute the above values only on problems where the model predicts that the answer is not "Unknown". Note, none of these metrics account for order of the reasoning steps.
Faithful Reasoning Using Large Language Models
Task 1 (2022) are not restricted to reasoning over knowledge in the context, but rather have the ability to hallucinate possibly incorrect "knowledge" to support the answer leading to reasoning traces which are not valid and cannot be trusted.
Faithful Reasoning Using Large Language Models
The EntailmentBank dataset proposed by Dalvi et al. (2021) has led to several works focused on deriving reasoning traces to backup an answer or hypothesis (Bostrom et al., 2022;Dalvi et al., 2022;Jhamtani and Clark, 2020;Ribeiro et al., 2022). In our work, we focus on answering questions and providing faithful reasoning traces, rather than post-hoc explanations.
Faithful Reasoning Using Large Language Models
With a similar motivation to our own, Gupta et al. (2022) and Nakano et al. (2021) show promising results extracting evidence from a table or the web, respectively, and using this to answer a question or solve a natural language inference (NLI) problem. However, while Gupta et al. (2022) and Nakano et al. (2021) show the evidence used, they do not show how that information was combined to answer the question. In our work, we produce a valid reasoning trace that shows how multiple pieces of knowledge are combined, over several iterations, to answer a question.
Faithful Reasoning Using Large Language Models
Other works have focused on using reasoning to show whether a statement is True or False (Betz  2021) train an LM to enumerate implications (and corresponding reasoning steps) given a hypothesis. A valid reasoning trace can be constructed from these outputs. However, this approach is limited to answering questions whose answer is True, False or Unknown, and a reasoning trace must be constructed post-hoc.
Faithful Reasoning Using Large Language Models
Finally, while several works have informally introduced the notion of faithful reasoning (Bostrom et al., 2022;Gupta et al., 2022;Kumar and Talukdar, 2020), we have related this more precisely to the definition of valid reasoning in logic.
Faithful Reasoning Using Large Language Models
The notion of valid and invalid reasoning traces have also been explored in the context of search. Jhamtani and Clark (2020) develop datasets of valid and invalid reasoning traces for grade school science questions. These can be used to train models to detect valid reasoning traces. However, it can be expensive to collect both valid and invalid reasoning traces hence they collect only shallow traces and their traces do not include intermediate inferences. Instead, we show how, given a valid reasoning trace, we can generate many invalid reasoning traces that can be used to finetune a value function and used to guide search. Also, rather than learning a verifier that evaluates a whole trace (Cobbe et al., 2021;Jhamtani and Clark, 2020;Nye et al., 2022), we train a model on partial reasoning traces, resulting in a model more similar to a value function which assesses the "value" of the current reasoning step, which can be used for step-level search.
Faithful Reasoning Using Large Language Models
Bostrom et al. (2022) also use step-level search to determine whether a hypothesis is entailed by a set of statements. While we perform a beam search, using a learned value function, to find high-quality reasoning traces, Bostrom et al.
Faithful Reasoning Using Large Language Models
(2022) depend on exhaustive search to evaluate all possible pairs of statements to use for selection. Unlike Bostrom et al. (2022), our selection step is not limited to selecting just two statements. This allows us to more efficiently solve Proof Writer tasks whose rules may be conditioned on multiple statements.
Faithful Reasoning Using Large Language Models
The problem of when to "stop" rarely features in the deep learning literature because our models typically answer problems in a single step. However, there are some exceptions. A simple example is text synthesis with large language models where the model has to determine when to stop producing tokens. This is often handled by a special 'End Of Sequence' token (Graves, 2013). Other examples in the deep learning literature draw random variables from a parameterised distribution to predict when to stop reasoning (Banino et al., 2021;Graves, 2016). Kadavath et al. (2022) also investigates when LMs "know" the answer. Their model proposes a number of candidates, and predicts whether each candidate is the answer to the question or not. Additionally, Bostrom et al. (2022) tackle the less challenging problem of determining whether an inference matches a goal state.
Faithful Reasoning Using Large Language Models
In summary, current work focuses on True/-False/NLI tasks (Bostrom et al., 2022;Dalvi et al., 2021;Tafjord et al., 2021) while our work tackles question-answering. This is not a trivial difference. In question-answering, there is less information with which to construct the reasoning trace, since the "goal" is not known, and learning when to terminate is also more challenging. Moreover, current work leverages reasoning traces to boost performance -rather than to aid explainability or build trust -allowing for hallucination of "knowledge" during reasoning (Kojima et al., 2022;Wei et al., 2022). Furthermore, some existing approaches still allow the opportunity for  Figure 10) mirrors the requirements for validity, see Table  10. Other approaches that do satisfy validity have their own limitations, as detailed above.
Faithful Reasoning Using Large Language Models
The causal structure of our model mirrors the requirements for producing a valid trace (Defn. 4). Requirements for a connected reasoning trace (Defn. 3) are guaranteed by design (Section 3.1.1). Unavoidably, given our use of LMs, we cannot guarantee that all reasoning steps will be logically correct (Defn. 4). However, our architecture is designed to encourage logical correctness by preventing models from 'cheating'. For exam-ple, if the Selection model selects two unrelated statements, then the Inference model may draw a nonsensical conclusion. We also mitigate this by introducing a learned value function (Section 3.3) that filters out poor reasoning traces, although this still cannot guarantee the correctness of every step. Examples of both correct and incorrect reasoning traces, along with their value (according to the value function), are shown in Section D.
Faithful Reasoning Using Large Language Models
In this paper we have focused on developing models that answer questions using valid reasoning. For now we have assumed access to a context, over which to reason. However, while there are some settings where such a context may be provided, in most real world settings this is unlikely. In this paper we have chosen to focus on the challenging problem of multi-step reasoning within a given context. However, in future work we hope to incorporate retrieval to populate the context, and there is already interesting research in this direction (Dalvi et al., 2021;Ribeiro et al., 2022;Xie et al., 2020).
Faithful Reasoning Using Large Language Models
Language models are being applied, with great success, to many different problems Alayrac et al.  (2022). However, they largely remain black boxes; we do not know how the models produce their responses. One solution to this is to develop models that can produce faithful reasoning traces. We characterise faithful reasoning in terms of logical validity (Section 2), and propose Selection-Inference, a model that mirrors the structure of this definition, and is guaranteed to produce valid reasoning traces under the assumption that individual steps are correct (Defn. 4). By fine-tuning an Inference model specifically for this task and preventing it from "cheating", we increase the likelihood that this assumption holds (Tables 7and 8). Finally, to find high-quality reasoning traces, we introduce a value function, and use it to guide a beam search through the tree of potential traces induced by the non-determinism of selection.
Faithful Reasoning Using Large Language Models
The resulting model achieves higher final an-swer accuracy than baseline models on both Proof Writer Tafjord et al. (2021) and Entailment-BankQA Dalvi et al. (2021) tasks. We see that both Proof Only and SI benefit from search (Tables 1 and 2). When compared to baseline models, our model is less likely to hallucinate facts while reasoning (Table 6 and 5). We see that the SI + Halter model is far more likely than baseline models to pay attention to the context (Table 3) and to leverage the reasoning trace (Table 4). Overall, we see that SI + Halter (+ Search) models achieves superior reasoning trace accuracy, especially on the more challenging tasks (Figures 8  and 9).
Faithful Reasoning Using Large Language Models
Our approach exemplifies a trend towards algorithmic prompting, a form of automated prompt engineering in which querying a language model becomes a computational primitive. The responses of the language model can be manipulated to construct new prompts that are then used to make further queries. Model queries and prompt construction are composed into algorithms with the usual computational constructs: sequence, choice, and iteration. Algorithmic prompting can be used to elicit more sophisticated and nuanced behaviour from a language model than would otherwise be possible. For example, as our work shows, this approach can be used to develop models capable of faithful reasoning, without compromising performance. In future work we aim to leverage advancements in retrieval to populate the context, rather than relying on the context being provided in the question. 
Faithful Reasoning Using Large Language Models
Formally, suppose we have a problem of the form ( , C 0 ), where C 0 is a context, consisting of a set of statements which are sufficient to predict the the correct answer to the question, .
Faithful Reasoning Using Large Language Models
The role of the Selection model, LM Selection is to sample a selection, , given the question, and the current context, C , see Equation 1.
Faithful Reasoning Using Large Language Models
The role of the Inference model, LM Inference is to sample an inference, , given the selection, , see Equation 2.
Faithful Reasoning Using Large Language Models
After each inference the context is updated as follows, C −1 ∪ −1 , accumulating inferences from previous steps of reasoning.
Faithful Reasoning Using Large Language Models
The Halter LM, LM halt , is applied to each inference, , in two ways. First, to choose whether the model should stop reasoning and the second to answer the question when the model is 'ready'. This is illustrated in Alg. 1 and Alg. 2.
Faithful Reasoning Using Large Language Models
The Proof Writer dataset (Tafjord et al., 2021) contains both a Closes and Open World Assumption version (CWA and OWA respectively). We use a subset of the OWA dataset. This is because for the CWA dataset everything that cannot be proven is considered False. This means that problems whose answer is False, do not have reasoning traces. On the other hand the OWA dataset contains proofs for problems whose answers are True and False. Those without proofs are "Unknown". Since we need proofs for training and evaluation, we use the problems from the OWA dataset that have accompanying proofs (i.e. those whose answer is not Unknown).    
Faithful Reasoning Using Large Language Models
In Table 5 we saw that baseline models, with the exception of EntailmentWriter, were more likely to hallucinate facts while reasoning on the EntailmentBank dataset than SI. Interestingly, Table 6 shows that Proof + Answer and Proof Only baseline models have learned not to make up facts while reasoning on the Proof Writer dataset. Note that both EntailmentWriter and SI (ours) are designed not to make up facts. Figure 18 shows the Rouge 1 scores between the predicted and ground truth, ordered, intermediate inferences. We see that EntailmentWriter is very good at single step inference on Task 1 problems, but performance quickly declines for problems requiring multiple steps of reasoning. In general SI models and models using halting and search outperform the baseline models.
Faithful Reasoning Using Large Language Models
Tables 7 and 8 show the accuracy of the Inference LM when fed valid selections.  If something needs the rabbit and it likes the bald eagle then the bald eagle is blue. If something likes the mouse then it is round. If something is rough and it does not see the mouse then it does not need the bald eagle. If something sees the mouse then it needs the rabbit. the rabbit likes the mouse. the bald eagle likes the rabbit. the rabbit likes the bald eagle. the rabbit sees the bald eagle. the rabbit is blue. the rabbit needs the bald eagle. the bald eagle needs the mouse. the rabbit needs the mouse. the mouse needs the bald eagle. the rabbit is not green. the bald eagle likes the mouse. the rabbit sees the mouse. the bald eagle is round. the bald eagle does not see the mouse. the rabbit is red. the rabbit is rough. Question: Does it imply that the statement "The bald eagle does not see the rabbit" is True?
Faithful Reasoning Using Large Language Models
If something sees the mouse then it needs the rabbit. We know that the rabbit sees the mouse. Therefore, the rabbit needs the rabbit. If something sees the mouse then it needs the rabbit. We know that the rabbit sees the mouse. Therefore, the rabbit needs the rabbit. If something sees the mouse then it needs the rabbit. We know that the rabbit sees the mouse. Therefore, the rabbit needs the rabbit. If something needs the rabbit and it likes the bald eagle then the bald eagle is blue. We know that the rabbit needs the rabbit and the rabbit likes the bald eagle. Therefore, the bald eagle is blue. If something is blue then it sees the rabbit. We know that the bald eagle is blue. Therefore, the bald eagle sees the rabbit. Answer: False Target Proof: If something sees the mouse then it needs the rabbit. We know that the rabbit sees the mouse. Therefore, the rabbit needs the rabbit. If something needs the rabbit and it likes the bald eagle then the bald eagle is blue. We know that the rabbit needs the rabbit and the rabbit likes the bald eagle. Therefore, the bald eagle is blue.
Faithful Reasoning Using Large Language Models
If something is blue then it sees the rabbit. We know that the bald eagle is blue. Therefore, the bald eagle sees the rabbit.
Faithful Reasoning Using Large Language Models
Example 2 (value: -8.6e-06)
Faithful Reasoning Using Large Language Models
If someone needs the bald eagle and the bald eagle needs the squirrel then the bald eagle likes the cow. If someone needs the squirrel then they are green.
Faithful Reasoning Using Large Language Models
If someone needs the cow and they need the dog then the cow is green. If someone likes the squirrel and they like the dog then the dog is nice. If someone sees the cow then they need the dog. If someone is cold then they see the cow. If someone needs the dog then the dog sees the cow.
Faithful Reasoning Using Large Language Models
If someone likes the dog and the dog is blue then the dog sees the bald eagle. the dog is nice. the cow is nice. the dog likes the squirrel. the squirrel likes the dog. the dog likes the cow. the squirrel sees the dog. the bald eagle is cold. the bald eagle sees the dog. the squirrel sees the bald eagle.
Faithful Reasoning Using Large Language Models
the dog sees the bald eagle. the squirrel needs the cow. the squirrel is cold. Question: Does it imply that the statement "The cow is not green" is True? Proof:
Faithful Reasoning Using Large Language Models
If someone is cold then they see the cow. We know that the squirrel is cold. Therefore, the squirrel sees the cow. If someone is cold then they see the cow. We know that the bald eagle is cold. Therefore, the bald eagle sees the cow. If someone sees the cow then they need the dog. We know that the squirrel sees the cow. Therefore, the squirrel needs the dog. If someone needs the cow and they need the dog then the cow is green. We know that the squirrel needs the cow and the squirrel needs the dog. Therefore, the cow is green.
Faithful Reasoning Using Large Language Models
If someone is cold then they see the cow. We know that the squirrel is cold. Therefore, the squirrel sees the cow. If someone sees the cow then they need the dog. We know that the squirrel sees the cow. Therefore, the squirrel needs the dog. If someone needs the cow and they need the dog then the cow is green. We know that the squirrel needs the cow and the squirrel needs the dog. Therefore, the cow is green. If something is red and it likes the tiger then it needs the dog. We know that the cat is red and the cat likes the tiger. Therefore, the cat needs the dog. If something needs the bald eagle then it eats the cat. We know that the tiger needs the bald eagle. Therefore, the tiger eats the cat. If something eats the cat then the cat needs the bald eagle. We know that the tiger eats the cat. Therefore, the cat needs the bald eagle. If something eats the cat and it needs the dog then the cat is cold. We know that the tiger eats the cat and the cat needs the dog. Therefore, the cat is cold. All cold things are nice. We know that the cat is cold. Therefore, the cat is nice. Answer: True Target Proof: If something needs the bald eagle then it eats the cat. We know that the tiger needs the bald eagle. Therefore, the tiger eats the cat. If something eats the cat then the cat needs the bald eagle. We know that the tiger eats the cat. Therefore, the cat needs the bald eagle.
Faithful Reasoning Using Large Language Models
If something needs the bald eagle then it eats the cat. We know that the cat needs the bald eagle. Therefore, the cat eats the cat.
Faithful Reasoning Using Large Language Models
If something is red and it likes the tiger then it needs the dog. We know that the cat is red and the cat likes the tiger. Therefore, the cat needs the dog. If something eats the cat and it needs the dog then the cat is cold. We know that the cat eats the cat and the cat needs the dog. Therefore, the cat is cold. All cold things are nice. We know that the cat is cold. Therefore, the cat is nice.
Faithful Reasoning Using Large Language Models
Example 4 (value: -1.0e-05)
Faithful Reasoning Using Large Language Models
If something is rough and it does not see the mouse then it does not need the bald eagle. If something needs the rabbit and it likes the bald eagle then the bald eagle is blue. If something sees the mouse then it needs the rabbit.
Faithful Reasoning Using Large Language Models
If something likes the rabbit and it sees the bald eagle then the bald eagle needs the rabbit. If something is blue then it sees the rabbit. If something likes the mouse then it is round. the rabbit needs the bald eagle. the rabbit likes the bald eagle. the bald eagle does not see the mouse. the bald eagle needs the mouse. the bald eagle likes the mouse. the mouse needs the bald eagle. the bald eagle likes the rabbit. the rabbit is red. the rabbit is rough. the rabbit is not green. the rabbit is blue. the rabbit likes the mouse. the rabbit sees the mouse. the bald eagle is round. the rabbit sees the bald eagle. the rabbit needs the mouse. Question: Does it imply that the statement "The bald eagle sees the rabbit" is True? Proof:
Faithful Reasoning Using Large Language Models
If something sees the mouse then it needs the rabbit. We know that the rabbit sees the mouse. Therefore, the rabbit needs the rabbit. If something sees the mouse then it needs the rabbit. We know that the rabbit sees the mouse.
Faithful Reasoning Using Large Language Models
Therefore, the rabbit needs the rabbit. If something needs the rabbit and it likes the bald eagle then the bald eagle is blue. We know that the rabbit needs the rabbit and the rabbit likes the bald eagle. Therefore, the bald eagle is blue.
Faithful Reasoning Using Large Language Models
If something is blue then it sees the rabbit. We know that the bald eagle is blue. Therefore, the bald eagle sees the rabbit. Answer: True Target Proof: If something sees the mouse then it needs the rabbit. We know that the rabbit sees the mouse. Therefore, the rabbit needs the rabbit. If something needs the rabbit and it likes the bald eagle then the bald eagle is blue. We know that the rabbit needs the rabbit and the rabbit likes the bald eagle. Therefore, the bald eagle is blue.
Faithful Reasoning Using Large Language Models
If something is blue then it sees the rabbit. We know that the bald eagle is blue. Therefore, the bald eagle sees the rabbit.
Faithful Reasoning Using Large Language Models
Example 5 (value: -1.0e-05)
Faithful Reasoning Using Large Language Models
If the mouse is young and the mouse likes the cat then the mouse chases the cat. If something likes the mouse and the mouse likes the tiger then the tiger likes the mouse. If the tiger is cold then the tiger sees the mouse. If something sees the mouse then it is young. If something chases the cat and it likes the cat then the cat sees the mouse. If something is young and it chases the mouse then it likes the cat. If something chases the tiger and the tiger likes the cat then the cat likes the mouse. If something sees the cat and it chases the cat then it likes the cat. the tiger is nice. the tiger sees the cat. the mouse chases the tiger. the tiger is red. the mouse is young. the mouse is round. the tiger likes the mouse.
Faithful Reasoning Using Large Language Models
the mouse is cold. the mouse is red. the mouse likes the cat. the cat chases the tiger. the tiger chases the mouse.
Faithful Reasoning Using Large Language Models
Does it imply that the statement "The cat is not young" is True?
Faithful Reasoning Using Large Language Models
If the mouse is young and the mouse likes the cat then the mouse chases the cat. We know that the mouse is young and the mouse likes the cat. Therefore, the mouse chases the cat. If the mouse is young and the mouse likes the cat then the mouse chases the cat. We know that the mouse is young and the mouse likes the cat. Therefore, the mouse chases the cat. If something chases the cat and it likes the cat then the cat sees the mouse. We know that the mouse chases the cat and the mouse likes the cat. Therefore, the cat sees the mouse. If something sees the mouse then it is young. We know that the cat sees the mouse. Therefore, the cat is young.
Faithful Reasoning Using Large Language Models
If the mouse is young and the mouse likes the cat then the mouse chases the cat. We know that the mouse is young and the mouse likes the cat. Therefore, the mouse chases the cat. If something chases the cat and it likes the cat then the cat sees the mouse. We know that the mouse chases the cat and the mouse likes the cat. Therefore, the cat sees the mouse. If something sees the mouse then it is young. We know that the cat sees the mouse. Therefore, the cat is young.
Faithful Reasoning Using Large Language Models
Example 6 (value: -1.0e-05)
Faithful Reasoning Using Large Language Models
If something eats the cow then it is green. If the bald eagle eats the mouse and the mouse is nice then the mouse is rough. If something needs the bald eagle then it is blue. If something chases the bald eagle and the bald eagle is rough then the bald eagle eats the cow.
Faithful Reasoning Using Large Language Models
If something is green and it needs the mouse then the mouse eats the cow. If something chases the bald eagle then the bald eagle is rough. If something chases the dog then the dog eats the cow. If something eats the dog and the dog chases the mouse then the dog needs the bald eagle. If something chases the cow and it is nice then the cow chases the mouse. the dog chases the cow. the dog eats the mouse. the cow chases the bald eagle. the dog is green. the cow is blue. the dog chases the bald eagle. the mouse needs the bald eagle. the bald eagle needs the mouse. the bald eagle is kind. the dog chases the mouse.
Faithful Reasoning Using Large Language Models
Does it imply that the statement "The mouse is green" is True?
Faithful Reasoning Using Large Language Models
If something is green and it needs the mouse then the mouse eats the cow. We know that the dog is green and the bald eagle needs the mouse. Therefore, the mouse eats the cow. If something eats the cow then it is green. We know that the mouse eats the cow. Therefore, the mouse is green. Answer: True Target Proof: If something chases the bald eagle then the bald eagle is rough. We know that the cow chases the bald eagle. Therefore, the bald eagle is rough. If something chases the bald eagle and the bald eagle is rough then the bald eagle eats the cow. We know that the cow chases the bald eagle and the bald eagle is rough. Therefore, the bald eagle eats the cow. If something eats the cow then it is green. We know that the bald eagle eats the cow. Therefore, the bald eagle is green. If something is green and it needs the mouse then the mouse eats the cow. We know that the bald eagle is green and the bald eagle needs the mouse. Therefore, the mouse eats the cow. If something eats the cow then it is green. We know that the mouse eats the cow. Therefore, the mouse is green.
Faithful Reasoning Using Large Language Models
Example 7 (value: -1.1e-05)
Faithful Reasoning Using Large Language Models
If someone eats the bald eagle then the bald eagle is not kind. the bear sees the cat. the cat eats the bald eagle. the lion sees the cat. the bald eagle sees the bear. the lion likes the bear. the cat likes the bald eagle. the bear does not eat the bald eagle.
Faithful Reasoning Using Large Language Models
Does it imply that the statement "The bald eagle is not kind" is True?
Faithful Reasoning Using Large Language Models
If someone eats the bald eagle then the bald eagle is not kind. We know that the cat eats the bald eagle. Therefore, the bald eagle is not kind. Answer: True Target Proof: If someone eats the bald eagle then the bald eagle is not kind. We know that the cat eats the bald eagle. Therefore, the bald eagle is not kind.
Faithful Reasoning Using Large Language Models
The question in this example asks the opposite question to that in Example 7, with the same context. Notice how the reasoning traces are the same and have the same value. The final answers are correct for each problem.
Faithful Reasoning Using Large Language Models
If someone eats the bald eagle then the bald eagle is not kind. the bald eagle sees the bear. the cat eats the bald eagle. the lion sees the cat. the cat likes the bald eagle. the bear sees the cat. the lion likes the bear. the bear does not eat the bald eagle.
Faithful Reasoning Using Large Language Models
Does it imply that the statement "The bald eagle is kind" is True? Proof: If someone eats the bald eagle then the bald eagle is not kind. We know that the cat eats the bald eagle. Therefore, the bald eagle is not kind. Answer: False Target Proof: If someone eats the bald eagle then the bald eagle is not kind. We know that the cat eats the bald eagle. Therefore, the bald eagle is not kind. Target Answer: False
Faithful Reasoning Using Large Language Models
If someone eats the squirrel and they like the rabbit then they are green. If someone sees the rabbit then they like the mouse. If someone likes the squirrel then they are kind. If someone likes the mouse and they like the rabbit then the mouse is red. If someone likes the squirrel then the squirrel likes the rabbit. If the squirrel likes the mouse and the mouse eats the squirrel then the mouse likes the squirrel. If someone eats the mouse and they eat the squirrel then the mouse is green. If someone is red then they eat the mouse. the rabbit is red. the mouse eats the rabbit. the squirrel sees the mouse. the mouse eats the squirrel. the rabbit likes the mouse. the squirrel is nice. the squirrel likes the mouse. the squirrel sees the rabbit. the mouse likes the rabbit. the rabbit sees the squirrel. the squirrel eats the rabbit. the rabbit eats the squirrel.
Faithful Reasoning Using Large Language Models
Does it imply that the statement "The mouse is not red" is True? Proof: If someone sees the rabbit then they like the mouse. We know that the squirrel sees the rabbit. Therefore, the squirrel likes the mouse. If someone likes the mouse and they like the rabbit then the mouse is red. We know that the squirrel likes the mouse and the mouse likes the rabbit. Therefore, the mouse is red. Answer: False Target Proof: If the squirrel likes the mouse and the mouse eats the squirrel then the mouse likes the squirrel. We know that the squirrel likes the mouse and the mouse eats the squirrel. Therefore, the mouse likes the squirrel. If someone likes the squirrel then the squirrel likes the rabbit. We know that the mouse likes the squirrel. Therefore, the squirrel likes the rabbit. If someone likes the mouse and they like the rabbit then the mouse is red. We know that the squirrel likes the mouse and the squirrel likes the rabbit. Therefore, the mouse is red. Target Answer: False
Faithful Reasoning Using Large Language Models
Context: If someone likes the mouse and the mouse sees the cow then they like the dog. If someone is green and they chase the lion then the lion chases the mouse. If the mouse does not like the lion then the mouse does not chase the lion. If the dog is young then the dog is round. If someone likes the lion then the lion likes the cow. If someone is green then they like the cow. If someone likes the cow and they are rough then the cow does not like the lion. If someone likes the cow then they chase the cow. the lion likes the cow. the cow sees the lion. the dog sees the mouse. the mouse chases the cow. the dog is green. the mouse does not chase the dog. the mouse is rough.
Faithful Reasoning Using Large Language Models
Does it imply that the statement "The dog does not like the cow" is True? Proof:
Faithful Reasoning Using Large Language Models
If someone is green then they like the cow. We know that the dog is green. Therefore, the dog likes the cow. Answer: False Target Proof: If someone is green then they like the cow. We know that the dog is green. Therefore, the dog likes the cow.
Faithful Reasoning Using Large Language Models
Below are examples of the worst five reasoning traces from SI + Halter + Search according to the value function. Errors are highlighted in red.
Faithful Reasoning Using Large Language Models
If something is kind then it likes the cow. If something likes the cow then the cow is kind. the cow is big. the mouse eats the bear. the tiger is kind. the bear visits the tiger.
Faithful Reasoning Using Large Language Models
Does it imply that the statement "The cow likes the cow" is True? Proof: If something is kind then it likes the cow. We know that the tiger is kind. Therefore, the tiger likes the cow. If something likes the cow then the cow is kind. We know that the tiger likes the cow. Therefore, the cow is kind. If something is kind then it likes the cow. We know that the cow is kind. Therefore, the cow likes the cow. Answer: True Target Proof: If something is kind then it likes the cow. We know that the tiger is kind. Therefore, the tiger likes the cow. If something likes the cow then the cow is kind. We know that the tiger likes the cow. Therefore, the cow is kind. If something is kind then it likes the cow. We know that the cow is kind. Therefore, the cow likes the cow.
Faithful Reasoning Using Large Language Models
If something needs the squirrel then the squirrel is cold. If something needs the lion then the lion likes the cat. If the lion needs the squirrel and the squirrel needs the lion then the lion eats the squirrel. If something likes the squirrel and the squirrel likes the cow then the cow is rough. If something is cold then it needs the squirrel. If something needs the squirrel and it eats the cat then the cat likes the squirrel. the cow is cold. the cat eats the cow. the lion eats the cow. the squirrel eats the lion.
Faithful Reasoning Using Large Language Models
Does it imply that the statement "The squirrel does not need the squirrel" is True? Proof: If something is cold then it needs the squirrel. We know that the cow is cold. Therefore, the cow needs the squirrel. If something needs the squirrel then the squirrel is cold. We know that the cow needs the squirrel. Therefore, the squirrel is cold. If something is cold then it needs the squirrel. We know that the squirrel is cold. Therefore, the squirrel needs the squirrel. Answer: False Target Proof: If something is cold then it needs the squirrel. We know that the cow is cold. Therefore, the cow needs the squirrel. If something needs the squirrel then the squirrel is cold. We know that the cow needs the squirrel. Therefore, the squirrel is cold. If something is cold then it needs the squirrel. We know that the squirrel is cold. Therefore, the squirrel needs the squirrel.
Faithful Reasoning Using Large Language Models
If someone is kind then they are rough. All cold, quiet people are smart.
Faithful Reasoning Using Large Language Models
If someone is cold then they are smart. If someone is blue then they are quiet. If someone is red and kind then they are smart. If someone is quiet then they are blue. All blue, smart people are red. Blue, rough people are red. If Gary is kind and Gary is rough then Gary is quiet. Fiona is smart. Charlie is kind. Fiona is blue. Bob is smart. Fiona is rough. Gary is kind. Charlie is not smart.
Faithful Reasoning Using Large Language Models
Does it imply that the statement "Gary is smart" is True? Proof: If someone is kind then they are rough. We know that Gary is kind. Therefore, Gary is rough. If someone is red and kind then they are smart. We know that Gary is kind and Gary is kind. Therefore, Gary is smart. Answer: True Target Proof: If someone is kind then they are rough. We know that Gary is kind. Therefore, Gary is rough. If Gary is kind and Gary is rough then Gary is quiet. We know that Gary is kind and Gary is rough. Therefore, Gary is quiet. If someone is quiet then they are blue. We know that Gary is quiet. Therefore, Gary is blue. If someone is kind then they are rough. We know that Gary is kind. Therefore, Gary is rough. Blue, rough people are red. We know that Gary is blue and Gary is rough. Therefore, Gary is red. If someone is red and kind then they are smart. We know that Gary is red and Gary is kind. Therefore, Gary is smart.
Faithful Reasoning Using Large Language Models
If something likes the cow then the cow is kind. If something is kind then it likes the cow. the cow is big. the tiger is kind. the mouse eats the bear. the bear visits the tiger.
Faithful Reasoning Using Large Language Models
Does it imply that the statement "The cow does not like the cow" is True? Proof: If something is kind then it likes the cow. We know that the tiger is kind. Therefore, the tiger likes the cow. If something likes the cow then the cow is kind. We know that the tiger likes the cow. Therefore, the cow is kind. If something is kind then it likes the cow. We know that the cow is kind. Therefore, the cow likes the cow. Answer: False Target Proof: If something is kind then it likes the cow. We know that the tiger is kind. Therefore, the tiger likes the cow. If something likes the cow then the cow is kind. We know that the tiger likes the cow. Therefore, the cow is kind. If something is kind then it likes the cow. We know that the cow is kind. Therefore, the cow likes the cow. Target Answer: False
Faithful Reasoning Using Large Language Models
If something is kind and not young then it eats the mouse. If something eats the mouse and the mouse eats the tiger then the mouse does not see the rabbit. If something needs the rabbit and the rabbit eats the tiger then the tiger sees the rabbit. If something is blue then it eats the mouse. If something eats the mouse then the mouse is blue. If something sees the tiger then it eats the rabbit. If the mouse is young and the mouse eats the bald eagle then the mouse needs the rabbit. If something sees the rabbit then the rabbit is not blue. the tiger is green. the bald eagle sees the tiger. the tiger is blue. the bald eagle is not blue. the rabbit is round. the rabbit is kind. the mouse is not kind. the bald eagle eats the rabbit. the tiger sees the rabbit. the bald eagle sees the mouse.
Faithful Reasoning Using Large Language Models
Does it imply that the statement "The mouse does not eat the mouse" is True? Proof: If something is blue then it eats the mouse. We know that the tiger is blue. Therefore, the tiger eats the mouse. If something eats the mouse then the mouse is blue. We know that the tiger eats the mouse. Therefore, the mouse is blue. If something is blue then it eats the mouse. We know that the mouse is blue. Therefore, the mouse eats the mouse. Answer: False Target Proof: If something is blue then it eats the mouse. We know that the tiger is blue. Therefore, the tiger eats the mouse. If something eats the mouse then the mouse is blue. We know that the tiger eats the mouse. Therefore, the mouse is blue. If something is blue then it eats the mouse. We know that the mouse is blue. Therefore, the mouse eats the mouse. Target Answer: False
Faithful Reasoning Using Large Language Models
Below are the top five examples of reasoning traces on EntailmentBankQA problems that require a single step of reasoning, ranked by their value according to our learned value function and are otherwise not cherry picked.
Faithful Reasoning Using Large Language Models
Context: a fly is a kind of insect an insect has six legs
Faithful Reasoning Using Large Language Models
An animal has six legs. What is it most likely to be? a spider OR a fly OR a lizard OR a centipede. Proof: a fly is a kind of insect. We know that an insect has six legs. Therefore, a fly has six legs. Answer: a fly Target Proof: a fly is a kind of insect. We know that an insect has six legs. Therefore, a fly has six legs. 
Faithful Reasoning Using Large Language Models
Below are the top five examples of reasoning traces on EntailmentBankQA problems that require two steps of reasoning, ranked by their value according to our learned value function and are otherwise not cherry picked.
Faithful Reasoning Using Large Language Models
Context: a runway is a kind of pathway for airplanes airports have runways for airplanes as the number of pathways increases , the traffic congestion in that area usually decreases Question:
Faithful Reasoning Using Large Language Models
Which of the following would be most effective in reducing air traffic congestion at a busy airport? providing performance feedback to pilots OR providing flight information to passengers OR increasing the number of aircraft at the airport OR increasing the number of runways at the airport. Proof: a runway is a kind of pathway for airplanes. We know that airports have runways for airplanes. Therefore, an airport runway is a kind of pathway for airplanes. an airport runway is a kind of pathway for airplanes. We know that as the number of pathways increases , the traffic congestion in that area usually decreases. Therefore, as the number of runways at a airport increases, the traffic congestion in that area usually decreases. Answer: increasing the number of runways at the airport Target Proof: a runway is a kind of pathway for airplanes. We know that as the number of pathways increases , the traffic congestion in that area usually decreases. Therefore, as the number of runways increases, the traffic congestion in that area usually decreases. as the number of runways increases, the traffic congestion in that area usually decreases. We know that airports have runways for airplanes. Therefore, as the number of runways increases, the traffic congestion at the airport usually decreases. tidal energy is a renewable resource. We know that wave energy is a renewable resource. Therefore, wave energy and tidal energy are both renewable resources. Answer: Wave energy is renewable Target Proof: tidal energy is a renewable resource. We know that tidal energy means energy from ocean tides. Therefore, energy from ocean tides is a renewable resource. energy from ocean tides is a renewable resource. We know that wave energy is a renewable resource. Therefore, wave energy and energy from ocean tides are both renewable resources. Target Answer: Both are renewable.
Faithful Reasoning Using Large Language Models
Context: light comes to the focal point after passing through a convex lens a convex lens causes light to refract and concentrate to magnify distant objects refraction is when light bends Question:
Faithful Reasoning Using Large Language Models
Which object is best used to demonstrate the bending of light as it passes through a substance? convex lens OR flat mirror OR opaque rod OR concave mirror.
Faithful Reasoning Using Large Language Models
light comes to the focal point after passing through a convex lens. We know that a convex lens causes light to refract and concentrate to magnify distant objects. Therefore, the lens causes light to refract and concentrate on the focal point. the lens causes light to refract and concentrate on the focal point. We know that refraction is when light bends. Therefore, the lens causes the light to bend towards the focal point. Answer: convex lens Target Proof: light comes to the focal point after passing through a convex lens. We know that a convex lens causes light to refract and concentrate to magnify distant objects. Therefore, a convex lens will cause the light to refract when the light passes through the convex lens. a convex lens will cause the light to refract when the light passes through the convex lens. We know that refraction is when light bends. Therefore, a convex lens will cause the light to bend when the light passes through the lens. against each other. We know that a hand is a kind of object and a student is rubbing his hands together. Therefore, friction will occur between the student's hands. friction will occur between the student's hands. We know that friction causes the temperature of an object to increase. Therefore, friction will cause the temperature of the student's hands to increase. Answer: This action produces thermal energy through friction Target Proof: friction occurs when two object 's surfaces move against each other. We know that a hand is a kind of object and a student is rubbing his hands together. Therefore, friction occurs when the student is rubbing his hands together. friction occurs when the student is rubbing his hands together. We know that friction causes the temperature of an object to increase. Therefore, friction causes the temperature of student's hands to increase. Target Answer: This action produces thermal energy through friction.
Faithful Reasoning Using Large Language Models
Context: receiving the recessive gene for a trait from each parent causes the offspring to express that recessive trait light eyes are a recessive trait for human jessica is a human with light eyes Question: If Jessica has light eyes (bb) and both of her parents have dark eyes (Bb), which statement is true? Jessica inherited both genes from her father. OR Jessica inherited both genes from her mother. OR Jessica inherited one recessive form of the gene from each parents from each parent. OR Jessica inherited one dominant from of the gene from each parent.. Proof: receiving the recessive gene for a trait from each parent causes the offspring to express that recessive trait. We know that light eyes are a recessive trait for human and jessica is a human with light eyes. Therefore, jessica received the recessive gene for light eyes from each parent. Answer: Jessica inherited one recessive form of the gene from each parent Target Proof: light eyes are a recessive trait for human. We know that jessica is a human with light eyes. Therefore, jessica has a recessive trait of light eyes. jessica has a recessive trait of light eyes. We know that receiving the recessive gene for a trait from each parent causes the offspring to express that recessive trait. Therefore, jessica received the recessive gene from each of her parent. Target Answer: Jessica inherited one recessive form of the gene from each parents from each parent.
Faithful Reasoning Using Large Language Models
Below are the top five examples of reasoning traces on EntailmentBankQA problems that require three steps of reasoning, ranked by their value according to our learned value function and are otherwise not cherry picked.
Faithful Reasoning Using Large Language Models
if something receives sunlight, then it will increase in temperature if something increases in temperature, then that something will be warm the air around the equator receives direct sunlight the air mass formed close to the ocean is humid in moisture Question: Which type of air mass forms over the ocean near the equator? moist and warm OR moist and cool OR dry and warm OR dry and cool. Proof: the air around the equator receives direct sunlight. We know that the air mass formed close to the ocean is humid in moisture. Therefore, the air mass formed close to the ocean would receive direct sunlight. the air mass formed close to the ocean would receive direct sunlight. We know that if something receives sunlight, then it will increase in temperature. Therefore, the air mass formed close to the ocean would increase in temperature. the air mass formed close to the ocean would increase in temperature. We know that if something increases in temperature, then that something will be warm. Therefore, the air mass formed close to the ocean would be warm. Answer: moist and warm Target Proof: if something receives sunlight, then it will increase in temperature. We know that the air around the equator receives direct sunlight. Therefore, the air around the equator will increase in temperature. the air around the equator will increase in temperature. We know that if something increases in temperature, then that something will be warm. Therefore, the air is warm around the equator. the air is warm around the equator. We know that the air mass formed close to the ocean is humid in moisture. Therefore, air masses formed over the ocean near the equator are moist / warm.
Faithful Reasoning Using Large Language Models
Context: sliding is a kind of movement friction occurs when two objects move against each other a rock is a kind of object a frozen pond is a kind of object a rock is slided across the frozen pond friction causes the speed of an object to decrease Question:
Faithful Reasoning Using Large Language Models
Kelly slides a flat rock across the smooth ice of a frozen pond. The rock slows down after several seconds. What causes the rock to slow down? The thickness of the ice OR The temperature of the air above the ice OR The force of friction between the ice and the rock OR The gravitational force between the ice and the rock. Proof: sliding is a kind of movement. We know that a rock is slided across the frozen pond and a rock is a kind of object. Therefore, the rock is slid across the frozen pond. the rock is slid across the frozen pond. We know that friction occurs when two objects move against each other and a rock is a kind of object and a frozen pond is a kind of object. Therefore, friction occurs when the rock is slid across the frozen pond. friction occurs when the rock is slid across the frozen pond. We know that friction causes the speed of an object to decrease and a rock is a kind of object. Therefore, friction will cause the speed of the rock to decrease when it is slid across the frozen pond. Answer: The force of friction between the ice and the rock Target Proof: sliding is a kind of movement. We know that a rock is slided across the frozen pond. Therefore, a rock is moving on the frozen pond. a rock is moving on the frozen pond. We know that friction occurs when two objects move against each other and a rock is a kind of object and a frozen pond is a kind of object. Therefore, friction will occur between the rock and the frozen pond. friction will occur between the rock and the frozen pond. We know that a rock is a kind of object and friction causes the speed of an object to decrease. Therefore, friction will cause the speed of the rock to decrease. Target Answer: The force of friction between the ice and the rock
Faithful Reasoning Using Large Language Models
Context: the parent cats have white fur white fur is white in color inheriting is when an inherited characteristic is passed from parent to offspring a cat is a kind of animal the color of / coloration of fur is an inherited characteristic animals produce offspring Question: Which trait would a cat most likely inherit from its parents? having a scar OR chasing a toy OR having white fur OR knowing its name.
Faithful Reasoning Using Large Language Models
inheriting is when an inherited characteristic is passed from parent to offspring. We know that the color of / coloration of fur is an inherited characteristic. Therefore, offspring can inherit the color of fur from parents. offspring can inherit the color of fur from parents. We know that the parent cats have white fur and white fur is white in color. Therefore, the offspring of the cats will inherit white fur from their parents. Answer: having white fur Target Proof: inheriting is when an inherited characteristic is passed from parent to offspring. We know that the color of / coloration of fur is an inherited characteristic. Therefore, the offspring will inherit the color of the fur of its parent. the offspring will inherit the color of the fur of its parent. We know that a cat is a kind of animal and animals produce offspring. Therefore, a cat will inherit the color of the fur of its parents. a cat will inherit the color of the fur of its parents. We know that the parent cats have white fur and white fur is white in color. Therefore, the cat will inherit the white colored fur from its parents. Target Answer: having white fur
Faithful Reasoning Using Large Language Models
Context: carbon is a kind of element a compound is made of two or more elements chemically combined calcium carbonate is made of calcium, carbon, and oxygen calcium is a kind of element oxygen is a kind of element Question: Calcium carbonate (CaCO 3 ) is considered a compound because it is made up of two or more molecules. OR elements. OR gases. OR solids..
Faithful Reasoning Using Large Language Models
carbon is a kind of element. We know that calcium is a kind of element and oxygen is a kind of element. Therefore, calcium, oxygen, and carbon are all elements. calcium, oxygen, and carbon are all elements. We know that calcium carbonate is made of calcium, carbon, and oxygen. Therefore, calcium carbonate is made of elements. Answer: elements Target Proof: carbon is a kind of element. We know that calcium is a kind of element and oxygen is a kind of element. Therefore, calcium, carbon, and oxygen are three elements. calcium, carbon, and oxygen are three elements. We know that calcium carbonate is made of calcium, carbon, and oxygen. Therefore, calcium carbonate is made of three elements. calcium carbonate is made of three elements. We know that a compound is made of two or more elements chemically combined. Therefore, calcium carbonate is a kind of compound. Target Answer: elements.
Faithful Reasoning Using Large Language Models
Context: trees takes in oxygen through roots close to the surface of the ground earthworms create tunnels in soil the looseness of soil increases the amount of oxygen in that soil tunnels in soil loosen that soil Question: Trees need oxygen. Roots close to the surface of the ground take in the oxygen the tree needs. Which organisms help trees get oxygen? woodpeckers making holes in the tree OR earthworms making holes in the ground near the tree OR mushrooms growing at the base of the tree OR squirrels eating walnuts on the ground near the tree. Proof: tunnels in soil loosen that soil. We know that the looseness of soil increases the amount of oxygen in that soil. Therefore, tunnels in soil increase the amount of oxygen in the soil. tunnels in soil increase the amount of oxygen in the soil. We know that trees takes in oxygen through roots close to the surface of the ground. Therefore, tunnels in soil increase the amount of oxygen that can be taken in through the roots of trees. tunnels in soil increase the amount of oxygen that can be taken in through the roots of trees.
Faithful Reasoning Using Large Language Models
We know that earthworms create tunnels in soil. Therefore, earthworms help trees get more oxygen through their roots by creating tunnels in the soil. Answer: earthworms making holes in the ground near the tree Target Proof: earthworms create tunnels in soil. We know that tunnels in soil loosen that soil. Therefore, earthworm can help loosen the soil by creating tunnels. earthworm can help loosen the soil by creating tunnels. We know that the looseness of soil increases the amount of oxygen in that soil. Therefore, earthworm creating tunnes can increase the amount of oxygen in the soil. earthworm creating tunnes can increase the amount of oxygen in the soil. We know that trees takes in oxygen through roots close to the surface of the ground. Therefore, more oxygen is available for tree roots. Target Answer: earthworms making holes in the ground near the tree
Faithful Reasoning Using Large Language Models
Below are the top five examples of reasoning traces on EntailmentBankQA problems that require a five steps of reasoning, ranked by their value according to our learned value function and are otherwise not cherry picked.
Faithful Reasoning Using Large Language Models
Context: woodpeckers live in forests animals adapt to their environment a squirrel is a kind of animal a woodpecker is a kind of bird squirrels live in forests a deer lives in a forest a deer is a kind of animal a forest is a kind of environment Question:
Faithful Reasoning Using Large Language Models
In which group of animals below are all of the members well adapted to living in a forest ecosystem? field mouse, rabbit, pheasant OR gull, tree frog, grasshopper OR coyote, antelope, bison OR squirrel, deer, woodpecker. Proof: a squirrel is a kind of animal. We know that a deer is a kind of animal. Therefore, a deer and a squirrel are kinds of animals. a deer and a squirrel are kinds of animals. We know that animals adapt to their environment. Therefore, a deer and a squirrel adapt to their environment. Answer: squirrel, deer, woodpecker Target Proof: a squirrel is a kind of animal. We know that squirrels live in forests. Therefore, squirrels are animals live in forests. a deer lives in a forest. We know that a deer is a kind of animal. Therefore, deer is an animal lives in a forest. woodpeckers live in forests. We know that a woodpecker is a kind of bird. Therefore, woodpeckers are animals live in forests. squirrels are animals live in forests. We know that deer is an animal lives in a forest and woodpeckers are animals live in forests. Therefore, squirrels and deer and woodpeckers are animals that live in forests. squirrels and deer and woodpeckers are animals that live in forests. We know that animals adapt to their environment and a forest is a kind of environment. Therefore, squirrels and deer and woodpeckers are adapted to living in forests. Target Answer: squirrel, deer, woodpecker
Faithful Reasoning Using Large Language Models
Context: toxic chemicals are dumped into a pond poisonous things can cause harm to organisms toxic chemicals are poisonous harming an organism can cause that organism to die a fish is a kind of organism a pond is a kind of body of water a fish lives in water Question:
Faithful Reasoning Using Large Language Models
Dumping toxic chemicals into a pond would most likely result in an increase in oxygen levels in the pond. OR plants near the pond growing more quickly. OR the toxic chemicals having no effect on the pond. OR fish in the pond being harmed or dying off.. Proof: a fish is a kind of organism. We know that harming an organism can cause that organism to die. Therefore, harming a fish can cause that fish to die. harming a fish can cause that fish to die. We know that poisonous things can cause harm to organisms. Therefore, poisonous things can cause fish to die. harming a fish can cause that fish to die. We know that poisonous things can cause fish to die. Therefore, poisonous things can harm fish. poisonous things can cause fish to die. We know that toxic chemicals are poisonous. Therefore, toxic chemicals can cause fish to die. Answer: fish in the pond being harmed or dying off Target Proof: toxic chemicals are dumped into a pond. We know that toxic chemicals are poisonous. Therefore, the pond is poisonous because of toxic chemicals. poisonous things can cause harm to organisms. We know that harming an organism can cause that organism to die. Therefore, poisonous things can cause organisms to die. a pond is a kind of body of water. We know that a fish lives in water. Therefore, fish live in ponds. fish live in ponds. We know that a fish is a kind of organism. Therefore, a fish is a kind of organism that lives in ponds. the pond is poisonous because of toxic chemicals. We know that poisonous things can cause organisms to die and a fish is a kind of organism that lives in ponds. Therefore, the pond with toxic chemicals can cause fish in the pond to die. Target Answer: fish in the pond being harmed or dying off.
Faithful Reasoning Using Large Language Models
In this example, the model makes a mistake on the first step of reasoning but is able to recover and does not use the incorrect inference in later steps.
Faithful Reasoning Using Large Language Models
Context: pulling a plow is a kind of chore a horse is a kind of animal an instinctive behavior is a kind of inherited characteristic inherited characteristics are the opposite of learned characteristics doing chores is a learned characteristic a learned characteristic is a kind of characteristic of an animal Question: Which of these is not an instinctive behavior? a bird building a nest OR a turtle burying its eggs OR a bear hibernating in winter OR a horse pulling a plow. Proof: doing chores is a learned characteristic. We know that inherited characteristics are the opposite of learned characteristics. Therefore, doing chores is an inherited characteristic. a horse is a kind of animal. We know that a learned characteristic is a kind of characteristic of an animal. Therefore, a learned characteristic of a horse is a kind of learned characteristic of an animal. pulling a plow is a kind of chore. We know that doing chores is a learned characteristic. Therefore, pulling a plow is a kind of learned characteristic. a learned characteristic of a horse is a kind of learned characteristic of an animal. We know that inherited characteristics are the opposite of learned characteristics. Therefore, a horse cannot inherit a learned characteristic. pulling a plow is a kind of learned characteristic. We know that a horse cannot inherit a learned characteristic. Therefore, a horse cannot inherit the characteristic of pulling a plow. Answer: a horse pulling a plow Target Proof: pulling a plow is a kind of chore. We know that doing chores is a learned characteristic. Therefore, pulling a plow is a learned characteristic. pulling a plow is a learned characteristic. We know that a learned characteristic is a kind of characteristic of an animal. Therefore, an animal pulling a plow is a kind of learned characteristic. an animal pulling a plow is a kind of learned characteristic. We know that a horse is a kind of animal. Therefore, a horse pulling a plow is a learned characteristic. an instinctive behavior is a kind of inherited characteristic. We know that inherited characteristics are the opposite of learned characteristics. Therefore, instinctive behaviors are opposite to learned characteristics. a horse pulling a plow is a learned characteristic. We know that instinctive behaviors are opposite to learned characteristics. Therefore, a horse pulling a plow is not an instinctive behavior. Target Answer: a horse pulling a plow
Faithful Reasoning Using Large Language Models
Context: disease-causing microbes have a negative impact on the body decreasing something negative has a positive impact on a thing destroying something decreases the amount of that something a source of something produces that something protecting a living thing has a positive impact on that living thing 's survival / health specialized cells are a source of chemicals that destroy disease-causing microbes Question: Specialized cells protect the human body from disease-causing microbes by producing chemicals that destroy the microbes OR dissolving wastes from the microbes OR creating recessive genes in the microbes OR supplying oxygen and nutrients to the microbes. Proof: disease-causing microbes have a negative impact on the body. We know that decreasing something negative has a positive impact on a thing. Therefore, decreasing disease-causing microbes has a positive impact on the body. decreasing disease-causing microbes has a positive impact on the body. We know that specialized cells are a source of chemicals that destroy disease-causing microbes. Therefore, as the number of specialized cells in the body increases, the number of disease-causing microbes being destroyed will increase.
Faithful Reasoning Using Large Language Models
Answer: creating recessive genes in the microbes Target Proof: a source of something produces that something. We know that specialized cells are a source of chemicals that destroy disease-causing microbes. Therefore, specialized cells produce chemicals that destroy disease-causing microbes. decreasing something negative has a positive impact on a thing. We know that destroying something decreases the amount of that something. Therefore, destroying something negative has a positive impact on a thing. destroying something negative has a positive impact on a thing. We know that disease-causing microbes have a negative impact on the body. Therefore, destroying disease-causing microbes has a positive impact on the body. destroying disease-causing microbes has a positive impact on the body. We know that protecting a living thing has a positive impact on that living thing 's survival / health. Therefore, destroying disease-causing microbes is a kind of method for protecting the body. specialized cells produce chemicals that destroy disease-causing microbes. We know that destroying disease-causing microbes is a kind of method for protecting the body. Therefore, specialized cells protect the body be producing chemicals that destroy disease-causing microbes. Target Answer: producing chemicals that destroy the microbes
Faithful Reasoning Using Large Language Models
Context: building materials are used to build buildings wood boards can be used to build houses a house is a kind of building wood is a renewable resource wood boards are made of wood a renewable resource is a kind of natural resource Question:
Faithful Reasoning Using Large Language Models
The building of houses in Maryland uses many different materials. Which building material is made of a renewable natural resource? copper wire OR steel beams OR wood boards OR plastic siding.
Faithful Reasoning Using Large Language Models
wood boards can be used to build houses. We know that wood is a renewable resource. Therefore, wood boards are a renewable resource that can be used to build houses. Answer: wood boards Target Proof: building materials are used to build buildings. We know that a house is a kind of building. Therefore, building materials can be used to build houses. building materials can be used to build houses. We know that wood boards can be used to build houses. Therefore, wood boards are a kind of building material. wood is a renewable resource. We know that a renewable resource is a kind of natural resource. Therefore, wood is a kind of renewable natural resource. wood is a kind of renewable natural resource. We know that wood boards are made of wood. Therefore, wood boards are made of a renewable natural resource. wood boards are a kind of building material. We know that wood boards are made of a renewable natural resource. Therefore, wood boards are a kind of building material that is made of a renewable natural resource. Target Answer: wood boards D.6. EntailmentBankQA Task 2 -depth 1: SI + Halter + Search
Faithful Reasoning Using Large Language Models
Below are the top three examples of reasoning traces on EntailmentBankQA problems that require a single step of reasoning, ranked by their value according to our learned value function and are otherwise not cherry picked.
Faithful Reasoning Using Large Language Models
Context: oil is a kind of energy resource gas is a kind of substance gasoline is a source of chemical energy chemical energy is a kind of potential energy an engine is a part of an automobile a fuel is used to make energy ethanol is a kind of substance as the use of a resource decreases , the length of time that resource being available will increases to give off means to be the source of potential energy means stored energy operating an automobile usually requires fossil fuels amount is a property of something and includes ordered values of none / least / little / some / half / much / many / most / all gasoline is a kind of chemical power source to run on means to use as an energy source using the fuel requires burning the fuel an energy source is a kind of resource using a gasoline engine requires burning gasoline best means most positive if the amount of electricity converted from the potential energy of an object is less than the amount of potential energy in the object , then the potential energy is converted into other energy other than electricity potential energy is a measure of the energy of an object due to position relative to other objects oil is a kind of substance / matter if an object / a substance makes something then that object / that substance is a source of that thing heat means heat energy an internal combustion engine is used to move the automobile if something requires something else then that something requires a source of that something else Question: Which of the following is the best example of potential energy? a fallen rock OR a burning match OR a liter of gasoline OR a red-hot piece of iron. Proof: gasoline is a kind of chemical power source. We know that using a gasoline engine requires burning gasoline. Therefore, using a gasoline engine requires burning chemical power source. using a gasoline engine requires burning chemical power source. We know that gasoline is a source of chemical energy. Therefore, using a gasoline engine requires burning chemical energy. using a gasoline engine requires burning chem-ical energy. We know that chemical energy is a kind of potential energy. Therefore, using a gasoline engine requires burning potential energy.
Faithful Reasoning Using Large Language Models
Answer: a liter of gasoline Target Proof: gasoline is a source of chemical energy. We know that chemical energy is a kind of potential energy. Therefore, gasoline is a source of potential energy. Target Answer: a liter of gasoline Example 2 (value: -0.023)
Faithful Reasoning Using Large Language Models
if heat is transferred to an object , then the object will get hot heat energy is synonymous with thermal energy a source of heat can be used to heat something greater means higher / more in value heat energy can be used to heat up an object if something causes an increase in something else then that something produces that something else if a body part was burned then that body part was exposed to a lot of heat energy as the temperature of a chemical reaction increases , the rate of the chemical reaction will increase adding heat means increasing temperature fanning increases the oxygen near the fire heat means heat energy warm up means increase temperature if something emits something else then that something increases the amount of that something else amount is a property of something and includes ordered values of none / least / little / some / half / much / many / most / all fire transfers heat through waves if a thermal conductor / an object is exposed to a source of heat then that conductor / that object may become hot / warm heat means the transfer of thermal energy heating means adding heat if heat is absorbed from a source then that heat source will cool increase means more as the amount of oxygen exposed to a fire increases, the fire will burn more heat is a kind of energy burning converts chemical energy into thermal energy combustion means fire converts chemical energy into light energy and heat energy thermal energy is a kind of energy Question:
Faithful Reasoning Using Large Language Models
Fanning can make a wood fire burn hotter because the fanning makes the food hot enough to burn OR adds more oxygen needed for burning OR increases the amount of wood there is to burn OR provides the energy needed to keep the fire going. Proof: fanning increases the oxygen near the fire. We know that as the amount of oxygen exposed to a fire increases, the fire will burn more. Therefore, as the amount of oxygen exposed to a fire increases, the fire will burn more quickly. as the amount of oxygen exposed to a fire increases, the fire will burn more. We know that fanning increases the oxygen near the fire. Therefore, fanning the fire increases the amount of burning woodchips. as the amount of oxygen exposed to a fire increases, the fire will burn more quickly. We know that fanning the fire increases the amount of burning woodchips. Therefore, fanning the fire increases the amount of oxygen exposed to the fire. as the amount of oxygen exposed to a fire increases, the fire will burn more quickly. We know that fanning the fire increases the amount of burning woodchips. Therefore, fanning the fire increases the amount of oxygen exposed to the fire. fanning the fire increases the amount of oxygen exposed to the fire. We know that as the amount of oxygen exposed to a fire increases, the fire will burn more quickly. Therefore, fanning the fire will cause the fire to burn more quickly. Answer: provides the energy needed to keep the fire going Target Proof: fanning increases the oxygen near the fire. We know that as the amount of oxygen exposed to a fire increases, the fire will burn more. Therefore, fanning can cause the fire to burn hotter. / 100 k / f / c to be found in means to be contained in freezing causes a solid to form melting is a kind of phase change state of matter at room temperature is a kind of physical property a physical property is a kind of property temperature / heat energy is a property of objects / weather and includes ordered values of cold / cool / warm / hot liquid has a a lower melting point than solid ice is colder in temperature than water temperature is a measure of heat energy matter in the solid phase has definite volume to be made of something means to be formed of that something matter in the liquid phase has definite volume the properties of something can be used to identify / used to describe that something Question: Which word best describes the physical state of an ice cube? gas OR solid OR liquid OR plasma.
Faithful Reasoning Using Large Language Models
an ice cube is a kind of solid. We know that solid is a kind of state of matter. Therefore, an ice cube is in solid state.
Faithful Reasoning Using Large Language Models
Answer: solid Target Proof: solid is a kind of state of matter. We know that an ice cube is a kind of solid. Therefore, an ice cube is solid in its physical state. Target Answer: solid
Faithful Reasoning Using Large Language Models
Context: oxygenated means having oxygen mitochondrion provide energy to cells using oxygen and glucose where something comes from is a source of that something sugar is a kind of food providing something means making / delivering something atp is formed by the breakdown of molecules of glucose if something has the ability to do something else , then that something can do that something else cells are a part of the body if something performs a task then that task is that something 's function to provide something means to be the source of that something cell division is a kind of process cell activity means cell process purpose means role oxygen can be found in air to provide means to supply atp supplies chemical energy for organisms to move both means two to have a function is similar to to be responsible for mitosis produces two cells with the same number of chromosomes as the parent cell all cells take in energy the function of something is what that something is used to do amount is a property of something and includes ordered values of none / least / little / some / half / much / many / most / all including means containing energy transformation means one kind of energy changes into another kind of energy a mitochondrion is a kind of cellular organelle Question: Which cellular organelle uses oxygen and glucose to provide energy to the cell? mitochondrion OR nucleus OR ribosome OR vacuole. Proof: mitochondrion provide energy to cells using oxygen and glucose. We know that a mitochondrion is a kind of cellular organelle. Therefore, mitochondrion is the cellular organelle that provides energy to cells using oxygen and glucose. Answer: mitochondrion Target Proof: mitochondrion provide energy to cells using oxygen and glucose. We know that a mitochondrion is a kind of cellular organelle. Therefore, mitochondrion is the cellular organelle that uses oxygen and glucose to provide energy to cells. Target Answer: mitochondrion
Faithful Reasoning Using Large Language Models
A random selection of five reasoning traces on Task 2 using SI + Halter, these include 'Unknown' examples where the model did not terminate its reasoning.
Faithful Reasoning Using Large Language Models
Context: electric currents produce magnetic fields knowing the properties of something means knowing information about that something luster is a property of an object / a material and includes ordered values of dull / shiny more likely means increased likelihood if something is a part of something else then that something else contains that something nitratine is always magnetic iron is a kind of element if something is a part of something then that something can be found in that something cadmium is always magnetic the metal is the core of electromagnet iron in contact with water and oxygen will rust the properties of something can be used to iden-tify / used to describe that something tungsten is a kind of metal steel / carbon steel is always ferromagnetic / magnetic iron is always magnetic iron nails are made of iron classifying means grouping objects / materials by their properties similar means in common a electromagnet is formed by attaching an iron nail wrapped in a copper wire to a circuit electric currents produce magnetic fields a magnetic field is a kind of force nickel is always ferromagnetic / magnetic cobalt is always ferromagnetic / magnetic magnetic force means magnetism the properties of something are used for describing that something Question: Which object most likely has magnetic properties? iron nail OR plastic clip OR rubber eraser OR wooden spoon. Proof: iron is always magnetic. We know that iron nails are made of iron. Therefore, iron nails are magnetic. Answer: iron nail Target Proof: iron is always magnetic. We know that iron nails are made of iron. Therefore, iron nails are magnetic. Target Answer: iron nails are magnetic
Faithful Reasoning Using Large Language Models
Context: celestial bodies / celestial objects are found in space if a condition is necessary for a process , then that condition make the process possible our sun is located at the center of our solar system gravity causes orbits to keep something occurring means to cause that something to occur exerting force on an object means a force acts on an object motion / movement means moving / to move isaac newton discovered the theory of gravity take place means happen planets in the solar system orbit the sun gravity means gravitational pull / gravitational energy / gravitational force / gravitational attraction can be means able to be both means two a force is a kind of push or pull on an object planets are found in space requiring something means needing that something revolving around something means orbiting that something mars is a kind of planet if something required by something else is in a place then that something else may be in that place to cause means to have an effect the sun is the strongest source of gravity in the solar system to depend on / to rely on / to need means to require to be used for something means to be required by that something orbit is a kind of characteristic due to means caused by Question:
Faithful Reasoning Using Large Language Models
The force necessary to keep planets in orbit around the Sun is gravity. OR friction. OR magnetism. OR nuclear.. Proof: planets in the solar system orbit the sun. We know that gravity causes orbits. Therefore, gravity causes the planets in the solar system to orbit the sun. Answer: gravity Target Proof: planets in the solar system orbit the sun. We know that gravity causes orbits. Therefore, gravity causes planets in the solar system to orbit the sun. Target Answer: gravity causes planets in the solar system to orbit the sun
Faithful Reasoning Using Large Language Models
Context: human eyes can only see light in the range of visible light classifying is when one sorts something by kind / type visible light is a part of the electromagnetic spectrum both means two if an object reflects a light of a certain color then the object appears to be that color category means kind made up of means contains / made of a type is synonymous with a kind electromagnetic energy travels as electromagnetic waves knowing the properties of something means knowing information about that something spectrum means a range of colors all waves transfer / transmit energy from one place to another the properties of something are used for describing that something radiation means radiant energy light means light energy electromagnetic radiation means electromagnetic energy light rays means light light is a kind of nonliving thing the properties of something can be used to identify / used to describe that something uv light is a kind of light the color of an object can be discovered by looking at that object amount is a property of something and includes ordered values of none / least / little / some / half / much / many / most / all visible light is made of lights of different colors including violet, blue, green, yellow, orange, red light if something is a part of something else then that something else contains that something color is a property of an object / a material Question:
Faithful Reasoning Using Large Language Models
The electromagnetic spectrum is the complete range of electromagnetic radiation ranging from radio waves to gamma rays. Which type of radiation in this spectrum is associated with observable colors such as red, green, and blue? gamma rays OR X-rays OR visible light OR radio waves. Proof: visible light is made of lights of different colors including violet, blue, green, yellow, orange, red light. We know that visible light is a part of the electromagnetic spectrum. Therefore, visible light is a part of the electromagnetic spectrum that includes violet blue green yellow orange and red light. Answer: visible light Target Proof: visible light is made of lights of different colors including violet, blue, green, yellow, orange, red light. We know that visible light is a part of the electromagnetic spectrum. Therefore, visible light is the part of electromagnetic spectrum that has red, green, and blue light. Target Answer: visible light is the part of electromagnetic spectrum that has red, green, and blue light
Faithful Reasoning Using Large Language Models
Context: to have a function is similar to to be responsible for to enable is to help providing support is a kind of function a function is a kind of characteristic a trunk is a part of a tree for supporting the tree if an organism can do something , then that organism is able to do that something bark is a protective covering around the trunk of / branches of a tree purpose means role role means function if something has the ability to do something else , then that something can do that something else to be used for something means to be required by that something to be used for something means to help to do that something a function is an activity the function of something is what that something is used to do a component of something means a part of that something essential means required ability is a property of things and includes ordered values of able / unable / can / cannot to anchor means to provide support role is similar to importance a cell wall provides support / protection / shape / structure for a plant cell something is used for that something 's purpose if something requires something else then that something else is important to that something helping means something can be done / completed more easily / better being used for is similar to providing function is similar to purpose Question:
Faithful Reasoning Using Large Language Models
The main function of a tree's trunk is to provide air OR fruit OR sunlight OR support.
Faithful Reasoning Using Large Language Models
a cell wall provides support / protection / shape / structure for a plant cell. We know that a trunk is a part of a tree for supporting the tree. Therefore, the cell wall is the part of a plant cell that supports the plant. the cell wall is the part of a plant cell that supports the plant. We know that bark is a protective covering around the trunk of / branches of a tree. Therefore, the cell wall is the part of a plant cell that protects the plant. the cell wall is the part of a plant cell that supports the plant. We know that bark is a protective covering around the trunk of / branches of a tree. Therefore, the cell wall is the part of a plant cell that protects the plant. the cell wall is the part of a plant cell that supports the plant. We know that bark is a protective covering around the trunk of / branches of a tree. Therefore, the cell wall is the part of a plant cell that protects the plant. the cell wall is the part of a plant cell that supports the plant. We know that bark is a protective covering around the trunk of / branches of a tree. Therefore, the cell wall is the part of a plant cell that protects the plant. the cell wall is the part of a plant cell that supports the plant. We know that bark is a protective covering around the trunk of / branches of a tree. Therefore, the cell wall is the part of a plant cell that protects the plant. Answer: Unknown Target Proof: providing support is a kind of function. We know that a trunk is a part of a tree for supporting the tree. Therefore, a function of a tree's trunk is to provide support. Target Answer: a function of a tree's trunk is to provide support
Faithful Reasoning Using Large Language Models
Context: metal is an electrical / electrical energy conductor can means having the ability to different materials usually have different properties material means substance to demonstrate means to exhibit characteristic means property iron is a kind of metal both means two ability is a property of things and includes ordered values of able / unable / can / cannot motion / movement means moving / to move if an object is made of something then the parts of that object are made of that something similar means in common a demonstration is similar to an example if something has the ability to do something else , then that something can do that something else what something is made of is a property of the organization or that something metal is flexible best means most positive the properties of something can be used to identify / used to describe that something property is similar to measurement a wire is usually made of metal a wire is a part of an electrical circuit for conducting electricity a property is a kind of information metal is a kind of substance the properties of something are used for describing that something an insulator is the opposite of a conductor Question: Flexibility is a physical property of some matter. Which of these materials best demonstrates the property of flexibility? a mirror OR a pencil OR a metal wire OR a telephone pole. Proof: metal is flexible. We know that a wire is usually made of metal. Therefore, metal is flexible and a wire is made of metal. Answer: a metal wire Target Proof: metal is flexible. We know that a wire is usually made of metal. Therefore, a metal wire is flexible. Target Answer: a metal wire is flexible
Faithful Reasoning Using Large Language Models
Below are example EntailmentWriter + Answer proofs on the Proof Writer dataset. We have replaced the sentence labels with the corresponding statements from the context and have not shown the context for brevity. We see that in each case the final conclusion answers the question, but using the incorrect reasoning. We see that the model often makes up inferences that do not follow, but do help the model solve the problem. Unlike SI, whose inference step does not have access to the question, EntailmentWriter has direct access to the question and therefore has the incentive to make up inferences that help to answer the questions even if they do not follow logically.
Faithful Reasoning Using Large Language Models
Question: Does it imply that the statement "The dog is big" is True? Reason: If something eats the bear then the bear needs the lion. We know that the dog eats the bear. Therefore, the bear needs the lion. If something needs the lion then the lion eats the bear. We know that the bear needs the lion. Therefore, the lion eats the bear. If the lion eats the bear then the bear does not eat the dog. We know that the lion eats the bear. Therefore, the bear does not eat the dog. If something is red and it does not eat the dog then the dog sees the rabbit. We know that the rabbit needs the dog and the bear does not eat the dog. Therefore, the dog sees the rabbit. If something sees the rabbit then it is not big. We know that the dog sees the rabbit. Therefore, the dog is not big.
Faithful Reasoning Using Large Language Models
Question: Does it imply that the statement "The dog does not chase the dog" is True?
Faithful Reasoning Using Large Language Models
Reason: If something chases the mouse then it is big. We know that the cow chases the mouse. Therefore, the cow chases the cow. If something chases the cow and it is big then it does not chase the dog. We know that the cow chases the mouse and the cow chases the cow. Therefore, the cow needs the dog. If something chases the cow then it needs the dog. We know that the cow chases the mouse. Therefore, the dog is nice.
Faithful Reasoning Using Large Language Models
If something needs the dog and it is nice then the dog is nice. We know that the dog is nice and the cow is nice. Therefore, the dog chases the cow.
Faithful Reasoning Using Large Language Models
If something is nice then it chases the cow. We know that the dog chases the cow. Therefore, the dog does not chase the dog.
Faithful Reasoning Using Large Language Models
Question: Does it imply that the statement "The cat sees the cat" is True? Reason: All nice things are young. We know that The cow is nice. Therefore, the cat is nice. If something is young and nice then it sees the cat. We know that the cat is nice and the cow is nice. Therefore, the cat is young. If something sees the cat and the cat needs the cow then cat is nice. We know that the cat is young and the cat needs the cow. Therefore, the cat sees the cat. Targets are shown in red. The underlined statement in the last line of the incorrect reasoning trace is the one that is substituted in. The Inference LM is used to compute the inference. It is very easy to see here that the second statement is incorrect because it contains a rule rather than a fact.  (a) Jaccard similarity between the GT intermediate steps and the predicted intermediate steps.
Faithful Reasoning Using Large Language Models
(b) Comparing the number of reasoning steps in the GT proof to those in the predicted proof.
Faithful Reasoning Using Large Language Models
(c) Intermediate inference accuracy where order of the inferences matters.
Faithful Reasoning Using Large Language Models
(d) Exact string match between the ground truth proof and the predicted proof.  
Natural Language Deduction through Search over Statement Compositions
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  Figure 1: An example of multi-step natural language deduction performed by our system. From input premises, our model generates new statements in a heuristic-guided way to try to prove a given hypothesis.
Natural Language Deduction through Search over Statement Compositions
accommodating models' affordances (Hase and Bansal, 2020;Bansal et al., 2021). A simple way of representing this kind of reasoning process is through an entailment tree : 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 . 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 (Jacovi and Goldberg, 2020).
Natural Language Deduction through Search over Statement Compositions
This paper proposes a system that factors the reasoning process into discrete search over intermediate steps. The core of our system is a arXiv:2201.06028v2 [cs.CL] 
Natural Language Deduction through Search over Statement Compositions
Winter has the least sunlight x 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " w j Q 1 y x Z M P d + R X I + e n 4 I l S a s f r C c = " > A A A C h n i c d V F d a 9 s w F J X d f W T e R 7 P t s S 9 i I Z B C M b b T 1 X s Z h L U P 2 9 M y W N p C b I w s y 6 m o J B t J H j H C P 2 V / a m / 7 N 5 X d D L p 2 u y B x d O 6 5 n K t 7 8 5 p R p Y P g t + P u P X r 8 5 O n o m f f 8 x c t X + + P X b 8 5 V 1 U h M V r h i l b z M k S K M C r L S V D N y W U u C e M 7 I R X 5 9 2 u c v f h C p a C W + 6 7 Y m K U c b Q U u K k b Z U N v 4 5 X c 4 S j v R V X p q 2 g w m n B f z z 3 n a H 3 j T R Z K s H H 5 O z h n T m L P v a 3 a X X c p O n J j g K / O M T e 8 X R y X 8 1 f n z U 6 + J e 8 M U K 2 o + h N 1 1 m g 0 5 y Q 0 T R z V A W W V e U z b 1 t F m b j S e A H Q 8 C H I N y B C d j F M h v / S o o K N 5 w I j R l S a h 0 G t U 4 N k p p i R j o v a R S p E b 5 G G 7 K 2 U C B O V G q G H j s 4 t U w B y 0 r a I z Q c 2 L s V B n G l W p 5 b Z T 8 h d T / X k / / K r R t d f k g N F X W j i c C 3 R m X D o K 5 g v x N Y U E m w Z q 0 F C E t q e 4 X 4 C k m E t d 2 c Z 4 c Q 3 v / y Q 3 A e + e H c j 7 4 d T x a f d u M Y g Q P w D s x A C G K w A J / B E q w A d v a c Q y d y 5 u 7 I 9 d 3 3 b n w r d Z 1 d z V v w V 7 i L G 9 t I v w c = < / l a t e x i t > December is during the winter in the northern hemisphere
Natural Language Deduction through Search over Statement Compositions
x 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " t 7 p x n 7 w n j K a 7 G y r Y l B z / K U Q u w 6 o = " > A A A C h n i c d V F d a 9 s w F J X d f W T e R 7 P t s S 9 i I Z B C M b b T 1 X s Z h L U P 2 9 M y W N p C b I w s y 6 m o J B t J H j H C P 2 V / a m / 7 N 5 X d D L p 2 u y B x d O 6 5 n K t 7 8 5 p R p Y P g t + P u P X r 8 5 O n o m f f 8 x c t X + + P X b 8 5 V 1 U h M V r h i l b z M k S K M C r L S V D N y W U u C e M 7 I R X 5 9 2 u c v f h C p a C W + 6 7 Y m K U c b Q U u K k b Z U N v 4 5 X c 4 S j v R V X p q 2 g w m n B f z z 3 n a H 3 j T R Z K s H H 5 O z h n T m L P v a 3 a X X c p O n J j g K / O M T e 8 X R y X 8 1 f n z U 6 + J e 8 M U K 2 o + h N 1 1 m g 0 5 y Q 0 T R z V A W W V e U z b 1 t F m X j S e A H Q 8 C H I N y B C d j F M h v / S o o K N 5 w I j R l S a h 0 G t U 4 N k p p i R j o v a R S p E b 5 G G 7 K 2 U C B O V G q G H j s 4 t U w B y 0 r a I z Q c 2 L s V B n G l W p 5 b Z T 8 h d T / X k / / K r R t d f k g N F X W j i c C 3 R m X D o K 5 g v x N Y U E m w Z q 0 F C E t q e 4 X 4 C k m E t d 2 c Z 4 c Q 3 v / y Q 3 A e + e H c j 7 4 d T x a f d u M Y g Q P w D s x A C G K w A J / B E q w A d v a c Q y d y 5 u 7 I 9 d 3 3 b n w r d Z 1 d z V v w V 7 i L G 9 z M v w g = < / l a t e x i t >
Natural Language Deduction through Search over Statement Compositions
The United States is located in the northern hemisphere
Natural Language Deduction through Search over Statement Compositions
x 3 < l a t e x i t s h a 1 _ b a s e 6 4 = " L / x t 5 S w X W 2 K A e 8 s V D 3 Z 5 n 4 q c n 2 c = " > A A A C h n i c d V F d a 9 s w F J X d f W T e R 7 P t s S 9 i I Z B C M b b T 1 X s Z h L U P 2 9 M y W N p C b I w s y 6 m o J B t J H j H C P 2 V / a m / 7 N 5 X d D L p 2 u y B x d O 6 5 n K t 7 8 5 p R p Y P g t + P u P X r 8 5 O n o m f f 8 x c t X + + P X b 8 5 V 1 U h M V r h i l b z M k S K M C r L S V D N y W U u C e M 7 I R X 5 9 2 u c v f h C p a C W + 6 7 Y m K U c b Q U u K k b Z U N v 4 5 X c 4 S j v R V X p q 2 g w m n B f z z 3 n a H 3 j T R Z K s H H 5 O z h n T m L P v a 3 a X X c p O n J j g K / O M T e 8 X R y X 8 1 f n z U 6 + J e 8 M U K 2 o + h N 1 1 m g 0 5 y Q 0 T R z V A W W V e U z b 1 t N s / G k 8 A P h o A P Q b g D E 7 C L Z T b + l R Q V b j g R G j O k 1 D o M a p 0 a J D X F j H R e 0 i h S I 3 y N N m R t o U C c q N Q M P X Z w a p k C l p W 0 R 2 g 4 s H c r D O J K t T y 3 y n 5 C 6 n 6 u J / + V W z e 6 / J A a K u p G E 4 F v j c q G Q V 3 B f i e w o J J g z V o L E J b U 9 g r x F Z I I a 7 s 5 z w 4 h v P / l h + A 8 8 s O 5 H 3 0 7 n i w + 7 c Y x A g f g H Z i B E M R g A T 6 D J V g B 7 O w 5 h 0 7 k z N 2 R 6 7 v v 3 f h W 6 j q 7 m r f g r 3 A X N 9 5 Q v w k = < / l a t e x i t > New York is a state in the United States of America
Natural Language Deduction through Search over Statement Compositions
x 4 < l a t e x i t s h a 1 _ b a s e 6 4 = " m y l b 6 N A / A t 0 j + C P c 5 g 2 x x d z d V o 4 = " > A A A C h n i c d V F d a 9 s w F J X d f W T e R 9 P t c S 9 i I Z B C M b a T 1 X s Z h G 0 P 2 9 M y W N p C b I w s y 6 m o J B t J L j H C P 2 V / a m / 7 N 5 P d D L p 2 u y B x d O 6 5 n K t 7 8 5 p R p Y P g l + M e P H j 4 6 P H o i f f 0 2 f M X h + O j l 2 e q a i Q m a 1 y x S l 7 k S B F G B V l r q h m 5 q C V B P G f k P L / 6 2 O f P r 4 l U t B L f d V u T l K O t o C X F S F s q G / + Y r m Y J R / o y L 0 3 b w Y T T A v 5 5 7 7 p j b 5 p o s t O D j 8 l Z Q z r z K f v a 3 a Y 3 c p u n J j g J / M W p v e L o 9 L 8 a P z 7 p d X E v + G I F 7 f v Q m 6 6 y Q S e 5 I a L o Z i i L r C v K 5 t 4 u W 2 T j S e A H Q 8 D 7
Natural Language Deduction through Search over Statement Compositions
v 3 y f X A W + e H c j 7 4 t J s s P + 3 G M w G v w B s x A C G K w B J / B C q w B d g 6 c Y y d y 5 u 7 I 9 d 2 3 b n w j d Z 1 9 z S v w V 7 j L 3 9 / U v w o = < / l a t e x i t > y 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " i v h 5 k k 8 j z a B q u E 5 t f 5 0 e u v y 0 a u U = " > A A A C h n i c d V F N a 9 w w E J W d f m z d j 2 z b Y y 6 i y 8 I G g r G 9 a Z x L Y E l z a E / d Q j c J r I 2 R Z X k j I s l G k k u M 8 E / p n 8 q t / 6 a y s 4 U 0 a Q c k n t 6 8 4 Y 1 m 8 p p R p Y P g l + P u P H n 6 7 P n o h f f y 1 e s 3 u + O 3 7 8 5 V 1 U h M V r h i l b z M k S K M C r L S V D N y W U u C e M 7 I R X 7 9 q c 9 f / C B S 0 U p 8 1 2 1 N U o 4 2 g p Y U I 2 2 p b P x z u p w l H O m r v D R t B x N O C / j n f d P t e 9 N E k x s 9 + J i c N a Q z Z 9 n X 7 j 6 9 l p s 8 N c F B 4 B 8 e 2 S u O j v 6 r 8 e O D X h f 3 g i 9 W 0 J 6 E 3 n S Z D T r J D R F F N 0 N Z Z F 1 R N v f a L M z G k 8 A P h o C P Q b g F E 7 C N Z T a + T Y o K N 5 w I j R l S a h 0 G t U 4 N k p p i R j o v a R S p E b 5 G G 7 K 2 U C B O V G q G H j s 4 t U w B y 0 r a I z Q c 2 P s V B n G l W p 5 b Z T 8 h 9 T D X k / / K r R t d H q e G i r r R R O A 7 o 7 J h U F e w 3 w k s q C R Y s 9 Y C h C W 1 v U J 8 h S T C 2 m 7 O s 0 M I H 3 7 5 M T i P / H D u R 9 8 O J 4 v T 7 T h G Y A 9 8 A D M Q g h g s w G e w B C u A n R 1 n 3 4 m c u T t y f f e j G 9 9 J X W d b 8 x 7 8 F e 7 i N 9 z O v w g = < / l a t e x i t >
Natural Language Deduction through Search over Statement Compositions
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 E = " > A A A C h n i c d V F N a 9 w w E J W d f m z d j 2 z b Y y 6 i y 8 I G g r G 9 a Z x L Y E l z a E / d Q j c J r I 2 R Z X k j I s l G k k u M 8 E / p n 8 q t / 6 a y s 4 U 0 a Q c k n t 6 8 4 Y 1 m 8 p p R p Y P g l + P u P H n 6 7 P n o h f f y 1 e s 3 u + O 3 7 8 5 V 1 U h M V r h i l b z M k S K M C r L S V D N y W U u C e M 7 I R X 7 9 q c 9 f / C B S 0 U p 8 1 2 1 N U o 4 2 g p Y U I 2 2 p b P x z u p w l H O m r v D R t B x N O C / j n f d P t e 9 N E k x s 9 + J i c N a Q z Z 9 n X 7 j 6 9 l p s 8 N c F B 4 B 8 e 2 S u O j v 6 r 8 e O D X h f 3 g i 9 W 0 J 6 E 3 n S Z D T r J D R F F N 0 N Z Z F 1 R N v f a L M r G k 8 A P h o C P Q b g F E 7 C N Z T a + T Y o K N 5 w I j R l S a h 0 G t U 4 N k p p i R j o v a R S p E b 5 G G 7 K 2 U C B O V G q G H j s 4 t U w B y 0 r a I z Q c 2 P s V B n G l W p 5 b Z T 8 h 9 T D X k / / K r R t d H q e G i r r R R O A 7 o 7 J h U F e w 3 w k s q C R Y s 9 Y C h C W 1 v U J 8 h S T C 2 m 7 O s 0 M I H 3 7 5 M T i P / H D u R 9 8 O J 4 v T 7 T h G Y A 9 8 A D M Q g h g s w G e w B C u A n R 1 n 3 4 m c u T t y f f e j G 9 9 J X W d b 8 x 7 8 F e 7 i N 9 5 S v w k = < / l a t e x i t >
Natural Language Deduction through Search over Statement Compositions
The United States has the least sunlight during the month of December step 1 step 2 x1, x3 < l a t e x i t s h a 1 _ b a s e 6 4 = " U c Y g n g T 6 K W + s i b i / 2 C o P 9 A / + l N s = " > A A A C q n i c d V F b a 9 s w G J W 9 W + f d 0 v V x L 2 I h L I V g b C c 0 f R m U b g / b w 1 h 2 S d J h G y H L c i o q 2 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 w = = < / l a t e x i t > x1, x4 < l a t e x i t s h a 1 _ b a s e 6 4 = " c J x W k 8 d X t K a A R G R u M h O W I Z 9 v m u I = " > A A A C q n i c d V F b a 9 s w G J W 9 W + f d 0 v V x L 2 I h L I V g b C c 0 f R m U b g / b w 1 h 2 S d J h G y H L c i o q 2 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 H q H B 0 H O 9 P u B t 4 O / B E O x j g Q Y / o 7 Q g l a C 5 J h w r F f p e q e M G S 8 0 I p 6 0 T V Y q W m F z h D Q 0 N z L G g K m 7 6 O V o 4 M k w K s 0 K a k 2 v Y s 9 c z G i y U q k V i n N 0 W 1 U 2 t I / + l h Z X O T u O G 5 W W l a U 5 2 h b K K Q 1 3 A 7 t 9 g y i Q l m t c G Y C K Z 6 R W S S y w x 0 e Z 3 H b M E / + b I t 8 E q c P 2 p G 3 y a D c / O 9 + s 4 A C / A S z A G P p i D M / A O L M A S E O u V 9 c F a W W t 7 Y n + 2 v 9 n h z m p b + 5 w j 8 F f Y 6 W + L w 8 s I < / l a t e x i t > x2, x3 < l a t e x i t s h a 1 _ b a s e 6 4 = " p S g 0 i m + H R C i C l E / C m j 5 t d c i + Y d 8 = " > A A A C q n i c d V F b a 9 s w G J W 9 W + f d 0 v V x L 2 I h L I V g b C c 0 f R m U b g / b w 1 h 2 S d J h G y H L c i o q 2 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 7 t D U z Q Y e q 7 X B 7 w N / D 0 Y g n 0 s 0 O B n l B a k E j T X h G O l Q t 8 r d d x g q R n h t H W i S t E S k y u 8 o a G B O R Z U x U 0 / R w t H h k l h V k h z c g 1 7 9 n p G g 4 V S t U i M s 9 u i u q l 1 5 L + 0 s N L Z a d y w v K w 0 z c m u U F Z x q A v Y / R t M m a R E 8 9 o A T C Q z v U J y i S U m 2 v y u Y 5 b g 3 x z 5 N l g F r j 9 1 g 0 + z 4 d n 5 f h 0 H 4 A V 4 C c b A B 3 N w B t 6 B B V g C Y r 2 y P l g r a 2 1 P 7 M / 2 N z v c W W 1 r n 3 M E / g o 7 / Q 2 L y M s I < / l a t e x i t > x2, x4 < l a t e x i t s h a 1 _ b a s e 6 4 = " o n K P q T 9 E p E 7 S p 0 3 k U 6 / D P J X q k G s = " > A A A C q n i c d V H L j t M w F H X C a w i v A k s 2 F l V F R 6 q i J K 2 m b J B G w A I W i P J o O y i J L M d x O t b Y S W Q 7 q F G U j + M X 2 P E 3 O G m Q h h m 4 k q 3 j c 8 7 V f T g p O V P a 8 3 5 Z 9 o 2 b t 2 7 f O b r r 3 L v / 4 O G j 0 e M n G 1 V U k t A 1 K X g h z x K s K G c 5 X W u m O T 0 r J c U i 4 X S b X L z p 9 O 1 3 K h U r 8 q + 6 L m k s 8 C 5 n G S N Y G w q N f k x W 0 0 h g f Z 5 k T d 3 C S L A U / n n v 2 2 N n E m m 6 1 3 2 d J u E V b Z u 3 6 G N 7 m Q 7 l L o k b b + a 5 i x N z L Y O T / 3 r c 5 a z z L T v D e 2 O o X / n O Z I V 6 n x Q N z d N 2 i l F g q m I 0 N z K a w 0 g x A U v 0 Z V o f e q t R M I N 7 t D h 2 9 g N C o 7 H n e n 3 A 6 8 A f w B g M s U K j 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 w u 8 I 6 G B u Z Y U B U 3 / R w t n B g m h V k h z c k 1 7 N n L G Q 0 W S t U i M c 5 u i + q q 1 p H / 0 s J K Z y / j h u V l p W l O D o W y i k N d w O 7 f Y M o k J Z r X B m A i m e k V k n M s M d H m d x 2 z B P / q y N f B J n D 9 u R t 8 W o x P X w / r O A L P w H M w B T 5 Y g l P w D q z A G h D r h f X B 2 l h b e 2 Z / t r / Z 4 c F q W 0 P O U / B X 2 O l v j U z L C Q = = < / l a t e x i t > x3, x4 < l a t e x i t s h a 1 _ b a s e 6 4 = " P Q A 5 X 8 / v G 7 q U 2 u R n K j F G f G 8 F r o w = " > A A A C q n i c d V F b a 9 s w G J W 9 W + f d 0 v V x L 2 I h L I V g b C c 0 f R m U b g / b w 1 h 2 S d J h G y H L c i o q 2 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
Natural Language Deduction through Search over Statement Compositions
x P 5 s f 7 P D n d W 2 9 j l H 4 K + w 0 9 + O 1 c s K < / l a t e x i t > y2, x4 < l a t e x i t s h a 1 _ b a s e 6 4 = " 8 Y 0 q s C o h B x / / + Y 2 L r N 0 V m A a q B m 4 = " > A A A C q n i c d V F b b 9 M w G H X C b Y T L C j z y Y l F V d F I V J W m 1 7 m X S B D z A A 6 J c 2 g 4 l k e U 4 T m f N T i L b Q Y 2 i / D j + A m / 8 G 5 y 0 k 8 Y G n 2 T r + J z z 6 b s 4 K T l T 2 v N + W / a d u / f u P z h 4 6 D x 6 / O T p 4 e D Z 8 5 U q K k n o k h S 8 k O c J V p S z n C 4 1 0 5 y e l 5 J i k X C 6 T i 7 f d v r 6 B 5 W K F f k 3 X Z c 0 F n i T s 4 w R r A 2 F B j 9 H i 3 E k s L 5 I s q Z u Y S R Y C q / e 2 / b I G U W a b n V f p 0 l 4 R d v m H f r U X q d D u U n i x p t 4 7 u z Y X P P g + L 8 e d z 7 p f P
Natural Language Deduction through Search over Statement Compositions
z p m C f 7 N k W + D V e D 6 U z f 4 P B u e v d m v 4 w C 8 B K / A G P h g D s 7 A e 7 A A S 0 C s 1 9 Z H a 2 W t 7 Y n 9 x f 5 u h z u r b e 1 z X o C / w k 7 / A I 7 X y w o = < / l a t e x i t > y1, y2 < l a t e x i t s h a 1 _ b a s e 6 4 = " j 7 9 5 e 0 N f
Natural Language Deduction through Search over Statement Compositions
h m 4 k q 1 z z z 1 X 9 5 V W n C n t + 7 8 s + 8 b N W 7 f v H N 1 1 7 t 1 / 8 P D R 6 P G T t S p r S e i K l L y U Z y l W l L O C r j T T n J 5 V k m K R c r p J L 9 7 0 8 c 1 3 K h U r i 6 + 6 q W g i 8
Natural Language Deduction through Search over Statement Compositions
e S n N K z Q c 2 M s Z L R Z K N S I 1 y n 6 L 6 m q s J / 8 V i 2 q d v 0 x a V l S 1 p g X Z F 8 p r D n U J + 7 v B j E l K N G 8 M w E Q y 0 y s k 5 1 h i o s 1 1 H b O E 4 O r I 1 8 E 6 9 I K Z F 3 6 a j 0 9 f H 9 Z x B J 6 B 5 2 A K A r A A p + A d W I I V I N Y L 6 4 O 1 t j a 2 a 3 + 2 v 9 n R X m p b h 5 y n 4 C + z s 9 + L z M s I < / l a t e x i t > fringe Execu+on of step 3: select top pair from fringe: y 2 , x 4 < l a t e x i t s h a 1 _ b a s e 6 4 = " 8 Y 0 q s C o h B x / / + Y 2 L r N 0 V m A a q B m 4 = " > A A A C q n i c d V F b b 9 M w G H X C b Y T L C j z y Y l F V d F I V J W m 1 7 m X S B D z A A 6 J c 2 g 4 l k e U 4 T m f N T i L b Q Y 2 i / D j + A m / 8 G 5 y 0 k 8 Y G n 2 T r + J z z 6 b s 4 K T l T 2 v N + W / a d u / f u P z h 4 6 D x 6 / O T p 4 e D Z 8 5 U q K k n o k h S 8 k O c J V p S z n C 4 1 0 5 y e l 5 J i k X C 6 T i 7 f d v r 6 B 5 W K F f k 3 X Z c 0 F n i T s 4 w R r A 2 F B j 9 H i 3 E k s L 5 I s q Z u Y S R Y C q / e 2 / b I G U W a b n V f p 0 l 4 R d v m H f r U X q d D u U n i x p t 4 7 u z Y X P P g + L 8 e d z 7 p f P
Natural Language Deduction through Search over Statement Compositions
z p m C f 7 N k W + D V e D 6 U z f 4 P B u e v d m v 4 w C 8 B K / A G P h g D s 7 A e 7 A A S 0 C s 1 9 Z H a 2 W t 7 Y n 9 x f 5 u h z u r b e 1 z X o C / w k 7 / A I 7 X y w o = < / l a t e x i t > sample from step model 
Natural Language Deduction through Search over Statement Compositions
o g x / l 3 7 H 3 3 b v 5 n s Z N C 1 2 w W J o 3 P P 5 V 6 d G x e c K e 1 5 v y z 7 y d N n z 1 9 s b T s v X 7 1 + s 9 N 7 + + 5 S 5 a U k d E 5 y n s v r
Natural Language Deduction through Search over Statement Compositions
A H x P p g n V i f r S / 2 n n 1 m n 9 s X a 6 l t b W r e g 7 / C / v 4 b w a L I F g = = < / l a t e x i t > Figure 2: Overview of the problem setting and our approach. The search fringe tracks which statements should be combined next, scored according to the heuristic h (indicated here by purple shading). See Algorithm 1 for a detailed account of the search procedure.
Natural Language Deduction through Search over Statement Compositions
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 . Thanks to our system's factored design and its ability to capitalize on additional semi-synthetic single step data (Bostrom et al., 2021), 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.
Natural Language Deduction through Search over Statement Compositions
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  in two settings of varying difficulty.
Natural Language Deduction through Search over Statement Compositions
The general setting we consider is shown in Figure  2. We assume we are given a collection of evidence sentences X = {x 1 . . . 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 1 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. is directly entailed by its children. Thus, if we can produce a tree with root g and leaves X, it follows that g is transitively entailed by the premises in X.
Natural Language Deduction through Search over Statement Compositions
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 (Yang et al., 2018;Chen et al., 2019) or models that build a proof structure but do not generate new statements (Saha et al., 2020(Saha et al., , 2021. We therefore require a generative step deduction model S to produce intermediate conclusions given their immediate children, a concept explored by  and Bostrom et al. (2021).
Natural Language Deduction through Search over Statement Compositions
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 m = 2 inputs. 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.
Natural Language Deduction through Search over Statement Compositions
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 Table 1.
Natural Language Deduction through Search over Statement Compositions
Our step models are instances of the T5 pretrained sequence-to-sequence model (Raffel et al., 2020) fine-tuned on a combination of deduction step datasets from prior work  Module Task data format (Datasets used)
Natural Language Deduction through Search over Statement Compositions
Step model S Single-step deductions (ParaPattern, EntailmentBank)
Natural Language Deduction through Search over Statement Compositions
Heuristic h Entailment trees* (EntailmentBank)
Natural Language Deduction through Search over Statement Compositions
Goal entailment model Single-sentence NLI (WANLI, EBEntail) Table 1: Each module in our proposed system operates independently, and most components can leverage existing resources without the need for full tree data. *Our best-performing parametric heuristic uses full tree supervision, but nonparametric heuristics are supported. Bostrom et al., 2021), which we discuss further in Section 4.4. At inference time, we decode from these models using nucleus sampling (Holtzman et al., 2020) with p = 0.9.
Natural Language Deduction through Search over Statement Compositions
We define a search procedure over sentence compositions that we call SCSEARCH, described in Algorithm 1. SCSEARCH is a best-first search procedure where the search fringe data structure is a max-heap of statement pairs ordered by the heuristic scoring function h. SCSEARCH iteratively combines statement pairs using the step deduction model, adding generated conclusions to the forest of entailed statements. The heuristic function h({x 1 . . . x m }, g) → R accepts candidate step inputs x i and a goal hypothesis g and returns a real-valued score indicating the priority of the potential step in the expansion order.
Natural Language Deduction through Search over Statement Compositions
These priority values reflect multiple factors. We want to prioritize compatible compositions: combining statements from which we can make a meaningful inference, as opposed to unrelated sentences. We also want to prioritize useful steps: among compatible compositions, we should prefer those that are likely to derive statements that help prove the hypothesis.
Natural Language Deduction through Search over Statement Compositions
We consider several potential realizations of the heuristic function h:
Natural Language Deduction through Search over Statement Compositions
Breadth-first Naively, the earliest fringe items are explored first; all compositions of initial premises will be explored before any composition involving an intermediate conclusion.
Natural Language Deduction through Search over Statement Compositions
Overlap This heuristic scores potential steps according to the number of tokens shared between input sentences. This heuristic is focused on compatibility, as overlap indicates expressions that might be unifiable (e.g., paper in the first composition step of Figure 1). In the Overlap+Goal version, token overlap with the goal hypothesis is also incorporated into the score.
Natural Language Deduction through Search over Statement Compositions
Repetition Past work on step deduction models (Bostrom et al., 2021) has identified that these models tend to "back off" to copying the input when given incompatible premises.
Natural Language Deduction through Search over Statement Compositions
This heuristic aims to exploit this behavior as a measure of premise compatibility. Potential steps are scored according to −p S (x 1 |x 1 ...x n ), i.e., the negative likelihood of repeating the first input.
Natural Language Deduction through Search over Statement Compositions
Learned This heuristic uses an additional pretrained model fine-tuned to predict whether input statements are part of a gold explanation of the hypothesis or not. We train this model on sets of step inputs drawn from a collection of valid steps augmented with negative samples produced by replacing one input with a random statement.
Natural Language Deduction through Search over Statement Compositions
The Learned+Goal version of this heuristic is also trained with the goal hypothesis in its input, so as to be able to select useful premises and guide search towards the goal. Note that the step model S which generates statements still does not see the goal; the goal only informs which compositions are explored first during the search. See Appendix A for training details of our learned heuristic models.
Natural Language Deduction through Search over Statement Compositions
In order to determine when the search has succeeded, we need a module to judge the  Figure 3: An example of the EntailmentWriter end-to-end system's linearized input and output format. EntailmentWriter takes the goal hypothesis as input, making it possible to hallucinate content based on it, and generation of → hypot may occur prematurely, before enough evidence is included to truly derive the goal.
Natural Language Deduction through Search over Statement Compositions
A fish is a kind of scaled animal that uses their scales to defend themselves. Scales are used for protection by fish. Entailment
Natural Language Deduction through Search over Statement Compositions
Information in an organism's chromosomes causes an inherited characteristic to be passed from parent to offspring by dna.
Natural Language Deduction through Search over Statement Compositions
Children usually resemble parents. Neutral
Natural Language Deduction through Search over Statement Compositions
A rheumatoid arthritis will happen first before other diseases affect the body's tissues.
Natural Language Deduction through Search over Statement Compositions
The immune system becomes disordered first before rheumatoid arthritis occurs. Neutral Table 2: Examples of instances from the EBENTAIL dataset. The goal hypotheses are from EntailmentBank, and the statements are from the SCSEARCH algorithm applied to the original EntailmentBank premises. Although the third example contains a contradiction, the 'neutral' and 'contradiction' labels are merged in EBENTAIL, as both reflect a failure to entail the goal. entailment relationship between each generated conclusion and the goal. We use a DeBERTa model (He et al., 2021) fine-tuned on the WANLI dataset (Liu et al., 2022) to predict the probability that each derived statement entails the goal. In order to mitigate the domain mismatch between WANLI and the scientific facts that make up EntailmentBank, we also fine-tune our goal entailment model on EBENTAIL, a set of 300 examples of generated conclusions sampled from SCSEARCH paired with corresponding goal hypotheses which we manually label for their entailment relationship.
Natural Language Deduction through Search over Statement Compositions
EBENTAIL To produce a set of reference judgments for threshold selection and entailment model evaluation, we sampled 150 instances of generated conclusions from SCSEARCH inference over EntailmentBank examples with their corresponding gold goals. Three annotators labeled the entailment relationship between these generated inferences and the goal. We select a consensus annotation with a majority vote. These examples form an in-domain evaluation set which we call EBENTAIL. To simultaneously train and evaluate on these judgements, we use 3-fold cross-validation where each cross-validation fold is constructed to contain goals not seen in its respective training fold. We extend EBENTAIL with EBENTAIL-ACTIVE, consisting of 150 additional instances with the lowest confidence (highest prediction entropy) following the initial fine-tuning, which are then manually labeled by at least one annotator.
Natural Language Deduction through Search over Statement Compositions
Thresholding During inference, rather than returning the highest-scoring class, a threshold value α is applied to the predicted probability of the 'entailment' class. This threshold allows for better control over trade-off between precision and recall. For our main experiments, we use an entailment score threshold of α = 0.81 selected via crossvalidation on EBENTAIL.
Natural Language Deduction through Search over Statement Compositions
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.
Natural Language Deduction through Search over Statement Compositions
We evaluate our models in two settings, both derived from the validation and test sets of the English-language EntailmentBank dataset. Each setting consists of a 1:1 mixture of examples with valid goals (the original EntailmentBank validation examples) and negative examples with invalid goals, produced by replacing the goal of each positive example with a distinct one drawn from another example. Each system is evaluated on whether it can prove the correct goals with valid steps and successfully reject incorrect goals.
Natural Language Deduction through Search over Statement Compositions
To construct hard negatives, candidate replacement goals are ranked according to TF-IDF weighted overlap between tokens in the destination example and tokens in their original example. For each negative example, the replacement goal with the highest overlap score is selected, excluding goals from examples whose premise sets are subsets of the destination example's premises. We manually check negative examples to ensure they cannot be derived from the provided premises.
Natural Language Deduction through Search over Statement Compositions
In Task 1, examples contain only gold premises (between 2 and 15), while in Task 2, each premise set is expanded to 25 premises through the addition of distractors retrieved from the original premise corpora. We set the maxSteps hyperparameter of the SCSEARCH algorithm to 20. The maximum gold tree step count in EntailmentBank is 17, so our approach can theoretically recover any binarized gold tree given the right heuristic scores.
Natural Language Deduction through Search over Statement Compositions
Note that we focus our evaluation on this goal discrimination task and validating that individual steps of entailment trees are correct, not on recovering the exact trees in EntailmentBank. Our deduction model frequently constructs correct entailment trees that do not match the reference, particularly since our approach is not trained endto-end on this dataset.
Natural Language Deduction through Search over Statement Compositions
We compare against an End-to-end T5 model that we train following the EntailmentWriter paradigm ). The EntailmentWriter system involves fine-tuning a sequence-to-sequence language model to generate an entire entailment tree in linearized form, conditioned on the concatenation of a set of premises and a hypothesis. The EntailmentWriter tree linearization format is shown in Figure 3. In the original work,  fine-tune T5-11b (Raffel et al., 2020); we replicate their training setup using T5-3b instead for parity with our other experiments.
Natural Language Deduction through Search over Statement Compositions
In order to evaluate whether an end-to-end model intrinsically distinguishes between valid and invalid entailment tree structures, we use the average output confidence over trees generated by the model trained without negative examples, computed as the mean token log-likelihood
Natural Language Deduction through Search over Statement Compositions
. This is motivated by the hypothesis that a model trained as a density estimator for trees composed of sound steps should assign low likelihood to unsound trees. We fit a linear model to predict the goal validity ∈ {0, 1} based on this quantity. We refer to this discriminative setup as End-to-end (Intrinsic).
Natural Language Deduction through Search over Statement Compositions
We also train a variant of the end-to-end baseline, End-to-end T5 (Classify), to explicitly predict whether a given goal is valid by including a flag token T or F at the start of the model's output. We augment the model's training data with an equal number of negative examples by randomly resampling goal hypotheses. We prepend T to the target sequence of positive examples, while the target sequence for negative examples is F. Note that this model can predict T and then output a nonsensical entailment tree, as the trees are posthoc explanations of the decision.
Natural Language Deduction through Search over Statement Compositions
For both Task 1 and Task 2, consistent models should be able to reach gold goals while also failing to prove invalid goals. To measure the former, we report the number of valid goals reached by each system as Goal%. For our search systems, this metric is computed as the proportion of positive examples for which any generated conclusion had a goal entailment score higher than the threshold α = 0.81 (see Section 4.4). Goal% scores for the end-to-end model correspond to its self-reported success rate -the proportion of positive examples for which the model emits the T token.
Natural Language Deduction through Search over Statement Compositions
We report the average number of steps expanded before reaching a valid goal as #Steps. This metric is averaged over examples for which a system is able to reach the goal.
Natural Language Deduction through Search over Statement Compositions
To measure whether systems are able to distinguish invalid goals from valid goals, we also compute precision-recall curves and report the area under the receiver operating characteristic (AUROC) of each system for both tasks. We produce these curves for search models by varying the goal entailment threshold α. For the End-toend (Intrinsic) model, we vary a threshold on the average generated token likelihood, and for the End-to-end (Classify) model, we vary a threshold on the value of p(T)/(p(T) + p(F)), the score assigned to the "valid" flag token by the model out the two possible validity flags.
Natural Language Deduction through Search over Statement Compositions
In addition to evaluating end-to-end performance through the above tasks, we would also like to understand the internal consistency of generated End-to-end (Classify) 100.0 ± 0.0 0.97 ± 0.00 2.8 ± 1.6 100.0 ± 0.0 0.95 ± 0.00 2.2 ± 1.2 End-to-end (Intrinsic) -0.57 ± 0.02 --0.62 ± 0.02 - Table 3: Results from our main experiments on the EntailmentBank test sets. Mean ± standard deviation is reported for each metric, taken across 10 trials varying the random seed used for nucleus sampling. Goal% indicates the proportion of valid goals reached by a system's generated trees using the α = 0.81 threshold. AUROC indicates the area under the receiver operating characteristic when attempting to distinguish gold goals from invalid goals. #Steps indicates the average number of steps expanded before reaching the goal among trees which reached valid goals; this metric's standard deviation is computed at the example level. See Section 4.3 for more details. 
Natural Language Deduction through Search over Statement Compositions
Step Validity
Natural Language Deduction through Search over Statement Compositions
Learned (Goal) 74.0% SCSearch 82.3% End-to-end 65.0% trees. To that end, we conduct a manual study of step validity. We sample 100 steps uniformly across valid-goal Task 2 examples for each of three systems: our full system, our system without mid-training, and the end-to-end system. The resulting set of 300 steps is shuffled and triply labeled by three annotators without knowledge of which examples came from which system. For each example, the annotators assess whether a single step's conclusion can be inferred from the input premises with minimal additional world knowledge. We discuss these results in Section 5.2.
Natural Language Deduction through Search over Statement Compositions
All sequence-to-sequence language models we experiment with are instances of T5-3b (Raffel et al., 2020) with 3 billion parameters. Bridging entailment models and learned heuristic models are derived from DeBERTa Large (He et al., 2021) with 350M parameters. Fine-tuning is performed with the Hugging Face transformers library (Wolf et al., 2020). Further details including fine-tuning hyperparameters are included in the appendix.
Natural Language Deduction through Search over Statement Compositions
Step deduction model We train our step deduction model using gold steps sampled from trees in the EntailmentBank (EB) training split, totaling 2,762 examples. Our full system, which we refer to as SCSearch, is also "mid-trained" on ParaPattern substitution data (Bostrom et al., 2021). The ParaPattern data is derived semi-synthetically from English Wikipedia, totaling ∼120k examples.
Natural Language Deduction through Search over Statement Compositions
In the mid-training configuration, an instance of T5 is fine-tuned for one epoch on the ParaPattern data and then for one epoch on the EntailmentBank data, after which optimal validation loss is reached.
Natural Language Deduction through Search over Statement Compositions
Learned heuristic models Data for our learned heuristic models is constructed by taking step inputs from the EntailmentBank training set's gold trees. For each positive step example, a corresponding negative example is produced by replacing one input statement with a sentence drawn at random from all statements in the training set that do not appear in the original step's subtree. Examples used to train the Learned (Goal) heuristic additionally contain the original step's gold goal concatenated to their input. Our full SCSearch system uses the Learned (Goal) heuristic.
Natural Language Deduction through Search over Statement Compositions
The results of our experiments on Task 1 and Task 2 are shown in Table 3. Table 4 shows the results of our manual step validity evaluation.
Natural Language Deduction through Search over Statement Compositions
The end-to-end approach is not a sound model of entailment tree structure. End-to-end T5 (Classify) is nominally able to "prove" 100% of gold goals by finishing a proof with -> hypot. However, as shown in Figure 4, using the generation confidence of End-to-end T5 to discriminate between valid goals and invalid goals (the Intrinsic method) is not much better than random chance, since the model has similar confidence when "proving" invalid goals as it does when generating trees for valid goals. This means that the model's output distribution does not penalize the generation of invalid steps.
Natural Language Deduction through Search over Statement Compositions
Our approach is able to prove most goals while exhibiting much better internal consistency than the end-to-end approach. Our full SCSearch system nearly matches the performance of the End-to-end (Classify) system on Task 1 and Task 2, losing chiefly in high-recall settings. Critically, Section 5.2 will show that it achieves a much higher rate of step validity in the process.
Natural Language Deduction through Search over Statement Compositions
Mid-training the step deduction model also increases the proportion of reachable valid goals by 3-5% (compare Learned (Goal) to SCSearch in Table 3). It is worth noting that the chosen threshold for our goal entailment module sacrifices recall in favor of avoiding false positives, as shown in Table 5, meaning that our reported Goal% rate is an underestimate. In Figure 4, we see that our SCSearch method can achieve 80% recall at roughly 80% precision with a slightly lower threshold.
Natural Language Deduction through Search over Statement Compositions
A goal-oriented heuristic is critical. If we compare Breadth-first, Repetition, our two Overlap methods, and our two Learned heuristics, both Table 3 and Figure 4 show that the incorporating goal information into the planning process is essential for Task 2, as only the Overlap (Goal) and Learned (Goal) heuristics are able to reach a reasonable number of valid goals in the presence of distractor premises. We can see in Figure 4 how much breadth-first degrades from Task 1 to Task 2, largely due to timing out.
Natural Language Deduction through Search over Statement Compositions
The most crucial divergence between our method and the end-to-end method arises in the evaluation of individual steps. The End-to-end (Classify) method can produce correct decisions, and as shown in Figure 3 it can always claim to have produced the goal statement, but is its reasoning sound? Table 4 shows that our best SCSearch model produces valid inferences 82% of the time, improving by 17% absolute over the end-to-end model as well as improving over the version of our system without mid-training on ParaPattern. This result confirms our hypothesis about the end-toend method: despite often predicting the right label and predicting an associated entailment tree, these entailment trees are not as likely to be valid due to their post-hoc nature and the conflation of search and generation.
Natural Language Deduction through Search over Statement Compositions
We can use our step validity rate to approximate the expected number of fully-valid trees based on the observed depth distribution. Under the conservative assumption that observed errors are distributed uniformly w.r.t. depth, the expected number of fully valid trees in a dataset D = {T 1 . . . T |D| } for validity rate v can be computed
Natural Language Deduction through Search over Statement Compositions
At a step validity rate of 82% we should expect ∼58% of trees generated by our system to be error-free. Under the same assumption, according to the end-to-end model's step validity rate we should expect only ∼35% of its trees to be fully valid.
Natural Language Deduction through Search over Statement Compositions
In Section 5.4 we examine observed error patterns in invalid steps. Crucially, even when our system produces a tree involving an invalid step, it is easy to audit the tree and determine exactly where the reasoning error occurred, since each step is conditioned only on its immediate premises. In contrast, the end-to-end model attends to all premises and the hypothesis at every step, meaning that when an inconsistent step is generated, it is difficult to diagnose the cause.  The results in Table 3 depend on an accurate assessment of when we have successfully deduced the hypothesis. To that end, we evaluate our goal entailment model against labeled test data. Table 5 shows the results of our evaluation on the EBENTAIL dataset described in Section 3.3. We view precision as more important than recall, as a stringent criteria for determining whether a tree has reached the goal increases confidence in our evaluation results. Our best F1 score, using EBENTAIL-ACTIVE, is only slightly lower than the lowest F1 score of the annotators when evaluated against the majority vote. Annotator agreement is moderate; macroaveraged inter-annotator F1 is 0.83 and Cohen's κ is 0.54. This indicates that the problem of determining when a statement straightforwardly entails the goal is subjective; the boundary between 'trivial' entailment and a case which needs an additional reasoning step is somewhat fuzzy.
Natural Language Deduction through Search over Statement Compositions
Although our step model cannot hallucinate based on the hypothesis, it can still fail to produce valid intermediate steps due to other challenges.
Natural Language Deduction through Search over Statement Compositions
One error type we see is indiscriminate unification: when given incompatible premises, the step model will sometimes still attempt to combine them, resulting in improper conclusions. For example, given the premises "Earthquake can change the earth's surface. In a short amount of time is similar to rapidly." one conclusion generated by the model is "Earthquake changes the earth's surface rapidly." This could be avoided through the use of more selective heuristics, or by explicitly supervising step models with negative examples in order to encourage conservative conclusions in these cases.
Natural Language Deduction through Search over Statement Compositions
We also observe compounding errors in conclusions generated from erroneous premises. For example, given the premises "Offspring will inherit a scar on both knees except not both knees. Offspring will inherit a scar on the knee from parents." the model generates "Parents will inherit a scar on both knees." This kind of relation assignment mistake is uncommon outside of instances involving bad premises. These errors could potentially be mitigated by training heuristics to avoid corrupted premises.
Natural Language Deduction through Search over Statement Compositions
An additional source of error arises from cases where the goal entailment model is unable to predict the correct entailment relationship between an output from the step model and the goal hypothesis.
Natural Language Deduction through Search over Statement Compositions
One reason this arises is definitional knowledge. When given the premise "Sugar is soluble in water," the model does not predict entailment of the goal hypothesis "Sugar cubes will dissolve in water when they are combined." English speakers who know the definition of 'soluble' and recognize that sugar cubes are made of sugar could reasonably understand this as entailed. However, the degree of definitional knowledge that should be expected of the entailment model is subjective and often a source of annotator disagreement.
Natural Language Deduction through Search over Statement Compositions
Another cause of errors are ill-formed statements. For example, the model predicts that "Lichens and soil are similar to being produced by breaking down rocks." entails "Lichens breaking down rocks can form soil." However, it is unclear what is "similar" in the generated statement due to poor syntax. Labels for examples like this often vary depending on how the annotator understood the step model's output. Improving the step model to reduce compounding generation errors will mitigate this issue.
Natural Language Deduction through Search over Statement Compositions
Finally, the entailment may sometimes be predicated on context. The model predicts that "A new moon will occur on june 30 when the moon orbits the earth." entails "The next new moon will occur on june 30." In this case, the model is assuming that 'a new moon' occurring is equivalent to 'the next new moon' occurring. Depending on annotator assumptions, cases like this can also be somewhat subjective.
Natural Language Deduction through Search over Statement Compositions
Future work could expand the training data of our NLI model to account for the subjectivity of NLI judgments (Pavlick and Kwiatkowski, 2019;Nie et al., 2020), particularly by modifying our data collection procedure (Zhang et al., 2021).
Natural Language Deduction through Search over Statement Compositions
Our work reflects an outgrowth of several lines of work in reading comprehension and textual reasoning. Multi-hop question answering models (Chen et al. 2019;Min et al. 2019;Nishida et al. 2019, 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.
Natural Language Deduction through Search over Statement Compositions
The NLProlog system (Weber et al., 2019) 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 Arabshahi et al. (2021). PRover (Saha et al., 2020) and ProofWriter  also frame natural language deduction as proof search, although both systems are evaluated in a synthetic domain of limited complexity. Betz and Richardson (2021) also use synthetic data to improve reasoning models through midtraining, although the improvements they observe are limited to premise selection performance. Hu et al. (2020) and  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 (MacCartney and Manning, 2009;Angeli et al., 2016) but is able to cover far more phenomena by relaxing the strict constraints of this framework. Finally, the Leap of Thought system (Talmor et al., 2020) tackles some related ideas in a discriminative reasoning framework.
Natural Language Deduction through Search over Statement Compositions
The recent chain-of-thought (Wei et al., 2022) and Scratchpads (Nye et al., 2021) methods also generate intermediate text as part of answer prediction.
Natural Language Deduction through Search over Statement Compositions
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 (Geva et al., 2021) they only mildly outperform a few-shot baseline.
Natural Language Deduction through Search over Statement Compositions
In this work, we propose a system that performs natural language reasoning through generative deduction and heuristic-guided search.
Natural Language Deduction through Search over Statement Compositions
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.
Natural Language Deduction through Search over Statement Compositions
The baseline approach we consider in this work, end-to-end modeling of entailment tree generation, enjoys the convenience of simple inference and quadratic complexity. However, the computational overhead of sequence-to-sequence models places a hard limit on the tree size and premise count that can be handled in the end-to-end setting; moreover, recent results call into question how well end-to-end Transformers can generalize this type of reasoning (Zhang et al., 2022). Our structured approach allows arbitrarily large premise sets and step counts. However, by discretizing the reasoning in the SCSearch procedure, we do face a runtime theoretically exponential in proof size to do exhaustive search. In practice, we limit our search to a finite horizon and find that this suffices to provide a practical wall clock runtime, never exceeding 5 seconds for any single example. Future work on higher tree depths may have to reckon with the theoretical limitations of this procedure, possibly through the use of better heuristics.
Natural Language Deduction through Search over Statement Compositions
Our experiments are conducted exclusively on English datasets. While we hypothesize that our approach would work equally well for another language given a pretrained sequence-to-sequence model for that language with equivalent capacity, such models are not available universally across languages, representing an obstacle for transferring our results to languages beyond English.
Natural Language Deduction through Search over Statement Compositions
Furthermore, the EntailmentBank dataset on which we train and evaluate targets the elementary science domain, raising a question of domain specificity. In future work, we plan to evaluate deduction models on additional datasets with different style, conceptual content, and types of reasoning in order to verify that the factored approach is equally applicable across diverse settings.
Natural Language Deduction through Search over Statement Compositions
Hugging Face transformers version: 4.19.1 Two NVidia Quadro 8000 GPUs were used for all experiments in this paper.
Natural Language Deduction through Search over Statement Compositions
Base model T5-3b Total batch size 8 Initial LR 5e-5 Epoch count 3 (early stopping on val. loss)     
Natural Language Deduction through Search over Statement Compositions
An ocean plant is a kind of water plant.
Natural Language Deduction through Search over Statement Compositions
A fossil of an ocean plant is found in the desert.
Natural Language Deduction through Search over Statement Compositions
If fossils of a water animal or plant are found in a place then that place used to be covered by water in the past.
Natural Language Deduction through Search over Statement Compositions
A fossil of a water plant is found in the desert. → goal: 0.02 Goal: The desert used to be covered by water in the past. → goal: 0.96