Natural Language Deduction with Incomplete Information

Introduction

Substantial prior work in domains like question answering Rajpurkar et al. (2016); Yang et al. (2018); Kwiatkowski et al. (2019), textual entailment Bowman et al. (2015); Williams et al. (2018); Nie et al. (2020), and other types of reasoning Clark et al. (2021); Dalvi et al. (2021) deals with making inferences from stated information, where we draw conclusions and answer questions based on textual context provided directly to a model. However, a growing body of research studies the problem of reasoning given incomplete information, especially for tasks labeled as commonsense reasoning Talmor et al. (2019); Rajani et al. (2019). Current approaches in these domains often work through latent reasoning by large language models Lourie et al. (2021), with only a few explicitly materializing the missing knowledge Bosselut et al. (2019); Bhagavatula et al. (2020); Arabshahi et al. (2021); Liu et al. (2022); Katz et al. (2022). However, making knowledge explicit is critical to make reasoning processes explainable: it allows users to critique those explanations and allows systems to reuse inferred knowledge across scenarios Dalvi et al. (2022).

The materialization of new knowledge is naturally formulated as abduction: generating an explanation given a premise and a conclusion. Abductive reasoning as a text generation task is fundamentally challenging, as it is an underspecified task with a large search space of valid generations, hence why prior work has framed it as a multiple-choice problem Bhagavatula et al. (2020). Nevertheless, the freeform generation setting is the one that real-world explainable reasoning systems are faced with.

In this paper, we develop an approach that combines abductive reasoning with multistep deductive reasoning. We build on recent discrete search-based approaches that construct entailment trees Dalvi et al. (2021); Bostrom et al. (2022); Yang and Deng (2021); Hong et al. (2022) to represent deductive inferences in natural language. Although more transparent than discriminative end-to-end models, these methods have so far required all necessary premises to be explicitly provided, and cannot account for abductive reasoning.

Our input is a set of incomplete premise facts and a goal; our algorithm searches forward from the premises and backwards from the goal to build a proof that entails the goal and recovers a missing premise through a combination of deductive and abductive inferences. Figure 1 shows an example. To constrain the model’s generation, we incorporate a validation criterion to test the consistency of each logical inference. We call this new system ADGV (Abduction and Deductive Generation with Validation, Figure 2). At its core, ADGV follows a similar heuristic search to Bostrom et al. (2022), iteratively generating conclusions and adding them to the search frontier, but incorporates abductive steps (analogous to backward-chaining) to make the search two-sided.

We evaluate on a new task variant that requires recovering a missing premise from a subset of textual evidence and a goal. We use two datasets: EntailmentBank Dalvi et al. (2021) and Everyday Norms: Why Not?, a new dataset that we construct that requires combining information about situations with general principles. We assess both coverage of held-out premises on our test examples and step validity of the steps used to construct them, thereby establishing the ability of ADGV to recover premises as well as construct entailment trees reaching the goal of the original example. Although our approach can reconstruct premises with a high validity rate, achieving high coverage has significant headroom for future work.

Our contributions are: (1) introduction of a new task for natural language understanding, recovering a premise in an underspecified entailment tree, along with a new dataset, Everyday Norms: Why Not?; (2) a new abductive step model and ADGV inference method, which combines forward and backward search; (3) new validation techniques that improve step validity in these models.

Problem Description

We study the task of generating a natural language proof tree $T$ that entails a goal $\mathbf{g}$ given a set of textual evidence $X=\{\mathbf{x}_{1}\dots\mathbf{x}_{n}\}$. Unique to our work, we remove one of the pieces of textual evidence $\mathbf{x}_{m}$ creating an underspecified setting where a deduction system operating over stated premises Dalvi et al. (2021); Bostrom et al. (2022) cannot build an entailment tree capable of reaching the goal. The task is then to prove the goal $\mathbf{g}$ while also recovering $\mathbf{x}_{m}$, which requires searching backwards from the goal to generate missing information. An overview of our abductive reasoning system can be seen in Figure 2.

Note that there is a trivial solution to this problem, which is to immediately assume that $\mathbf{x}_{m}=\mathbf{g}$, leading to a vacuous proof. There is no easy way to rule out this solution, as it is hard to come up with a first-order principle for what makes an atomic premise. In existing datasets like EntailmentBank Dalvi et al. (2021), premises can be low-level definitions (“revolving around means orbiting”) or more complex process descriptions (“Photosynthesis means producers / green plants convert from carbon dioxide and water and solar energy into carbohydrates and food and oxygen for themselves”). Other past work Dalvi et al. (2022); Weir and Van Durme (2022) has use large language models to determine atomicity, but this also fails to yield a consistent principle beyond preferring statements that are attested in large web corpora.

Methods

Our approach is based on two generative modules called step models. Our deductive step model $S_{d}$ defines a probability distribution $P_{S_{d}}(\mathbf{y}\ |\ \mathbf{x}_{1}\dots\mathbf{x}_{n})$ over valid conclusions $\mathbf{y}$ given premises $\mathbf{x}_{1}\dots\mathbf{x}_{n}$, all of which are represented as natural language strings. We use the same notion of deduction as in past work Bostrom et al. (2021), where the model should place probability mass over correct and useful conclusions that can be inferred from the premises (i.e., not simply copying a premise). Following past work, we set $n=2$, which we find sufficient to handle both of our datasets.

New in this work, we additionally introduce an abductive step model $S_{a}=P_{S_{a}}(\mathbf{x^{\prime}}\mid\mathbf{x}_{1}\dots\mathbf{x}_{n},\mathbf{c})$. This model is meant to “reverse” the behavior of the forward model in a similar fashion as backward-chaining in Prolog Robinson (1965). Specifically, it takes a conclusion statement $\mathbf{c}$ as well as one premise $\mathbf{x}$ and generates a hypothesis $\mathbf{x^{\prime}}$. The generated hypothesis, $\mathbf{x^{\prime}}$, constitutes a new piece of information that the step model infers is necessary to make the original conclusion $\mathbf{c}$ true. This operation can then be chained repeatedly to uncover more general and abstract information. We find in our work that setting $n=1$ (one premise and a conclusion $\mathbf{c}$) is sufficient.

Deductive inferences in the domains we consider may be lexically underspecified, but typically represent a clear logical operation. However, abduction does not. An example can be seen in Figure 3: the abductive model can produce multiple valid generations at varying levels of specificity. Determining the truth of these generations is extremely challenging as in other work that tries to generate intermediate unstated inferences Rajani et al. (2019); Wiegreffe et al. (2022); Dalvi et al. (2022); Liu et al. (2022). To mitigate this, we introduce round-trip validators which enforce the condition that the forward and abductive models’ generations must agree.

Our system revolves around structuring the application of the two step models, $S_{d}$ and $S_{a}$, with a search procedure. We first describe the mechanics of the step models and then the heuristic search procedure, which employs two heuristics $H^{d}$ and $H^{a}$ to guide which step generation to perform next.

Both models are trained on data from EntailmentBank Dalvi et al. (2021). Following Bostrom et al. (2022), we do not rely on complete trees from EntailmentBank to train the step models, but instead view a tree $T$ as a collection of steps $T_{i}=(\mathbf{x}_{i,1},\ldots,\mathbf{x}_{i,n}\rightarrow\mathbf{c}_{i})$.

1 Step Models

Our abductive step model is an instance of a pre-trained language model. We specialize it to map from a conclusion statement and a single premise to a hypothesized missing premise, yielding the distribution $p_{S_{a}}(\mathbf{x^{\prime}}\mid\mathbf{x},\mathbf{c})$.

The abductive step model is trained on the EntailmentBank dataset by converting each step $T_{i}=(\mathbf{x}_{1},\mathbf{x}_{2}\rightarrow\mathbf{c})$ into multiple abductive steps by ablating each input in turn: $\mathbf{x}_{1},\mathbf{c}\rightarrow\mathbf{x}_{2}$ and $\mathbf{x}_{2},\mathbf{c}\rightarrow\mathbf{x}_{1}$. We ensure the conclusion $\mathbf{c}$ is always appended at the end of the input so the model can learn asymmetric relationships between premises and the input conclusion. The model is trained with teacher forcing to generate exactly the correct premise; however, during inference we sample as many as $k=40$ generations from the abductive model to account for underspecification.

Our deductive step model follows Bostrom et al. (2022) and is trained in a similar fashion as the abductive step model. We fine-tune a pretrained language model to map a set of premises to a conclusion statement, giving the distribution $p_{S_{d}}(\mathbf{c}\mid x_{1},...,x_{n})$. This model is trained on the EntailmentBank dataset only (not using data from Bostrom et al. (2021)), using intermediate steps $T_{i}\ {=}\ (\mathbf{x}_{1},\mathbf{x}_{2}\rightarrow\mathbf{c})$ as training examples. During inference, we sample as many as $k^{\prime}\ {=}\ 10$ generations from the deductive model to account for underspecification.

2 Search

During search, we order the entries in the deductive fringe according to the Learned (Goal) heuristic model from Bostrom et al. (2022). For the abductive fringe, however, we train a custom learned heuristic.Note that adding goal conditioning to an abductive heuristic does not make sense as the model typically already has knowledge of the goal in its inputs.

To train the abductive heuristic, we produce a pool of positive abductive steps from the gold EntailmentBank train dataset by selecting an arbitrary intermediate step and pairing each of its inputs with the step’s conclusion to yield a single positive example. We also produce negative samples by pairing an intermediate conclusion $\mathbf{c}$ and an arbitrary premise or other intermediate conclusion that is not part of $\mathbf{c}$’s subtree (previous inputs). The heuristic model is an instance of DeBERTa-v3 Large finetuned on all positive and negative samples. Further details are in the appendix.

Generating and Filtering

We allow for multiple generations to be sampled per step to fully explore the search space; however, this may lead to either invalid or redundant generations that need to be pruned. A combination of validators $V(inputs,\mathbf{y}_{i})$ remove any generations that do not meet a set of criteria, pruning their branch in the search space. The fringe is then populated using the valid generations following the rules in Table 6.

Our core validation methods to ensure logical correctness rely on a notion of round-trip consistency: we want deductive generations to work in reverse when plugged into the abductive model, and vice versa. More specifically, our Deductive Agreement module validates abductive steps, ensuring that the abductive generation (when combined with its input premise) produces the original conclusion. For example, the abductive step $(\mathbf{c},\mathbf{x}\ {\rightarrow}\ \mathbf{x^{\prime}})$ is validated by taking the corresponding deductive step $(\mathbf{x},\mathbf{x^{\prime}}\ {\rightarrow}\ \mathbf{c}^{\prime})$. The validator then checks that the scoring metric $E(\mathbf{c},\mathbf{c^{\prime}})$ is above a set threshold $t_{d}$.

The Abductive Agreement validator ensures that each input of a deductive step can be recovered using the output of the deductive step and the other input. For example, the deductive step $(\mathbf{x}_{1},\mathbf{x}_{2}\ {\rightarrow}\ \mathbf{c})$ is validated by taking two corresponding abductive steps $(\mathbf{x}_{1},\mathbf{c}\ {\rightarrow}\ \mathbf{x}_{2}^{\prime})$ and $(\mathbf{x}_{2},\mathbf{c}\ {\rightarrow}\ \mathbf{x}_{1}^{\prime})$. The scoring metric is then checked for the two pairs $E(\mathbf{x}_{1},\mathbf{x}_{1}^{\prime})$ and $E(\mathbf{x}_{2},\mathbf{x}_{2}^{\prime})$. Both generated inputs’ scores must be above a threshold $t_{a}$ for the output to be considered valid.

Other Validation Methods

We also used two other validators: de-duplication and consanguinity thresholding. De-duplication removes any non-unique outputs as well as any output that is copied directly from the inputs of the step. Consanguinity thresholding looks at the “ancestry” of a generation up to depth $\eta$ and blocks generating from any pair that shares a given statement in their ancestry. We set $\eta=1$ to prevent combination of two of the same statement; higher thresholds did not help.

3 Premise Recovery Scoring

When the search concludes, we score each abductive generation $\mathbf{x^{\prime}}$ to test for the recovery of $\mathbf{x}_{m}$ through a scoring metric $E(\mathbf{x^{\prime}},\mathbf{x}_{m})$ which we then filter to candidates that pass a threshold $t_{m}$. To score each abduction, our system uses a harmonic mean $s=E(\mathbf{x}_{m},\mathbf{x^{\prime}})=\frac{2s_{r}s_{e}}{s_{r}+s_{e}}$ of $s_{r}=\textrm{ROUGE-1}(\mathbf{x}_{m},\mathbf{x^{\prime}})$ and an entailment scoring $s_{e}=entailed(\mathbf{x^{\prime}},\mathbf{x}_{m})$ according to an entailment model. Every $\mathbf{x^{\prime}}$ that recovers $\mathbf{x}_{m}$ has exactly one corresponding derivation that entails the goal, so we can associate it with a deductive proof tree.

4 Re-Ranking Proofs

Each proof found is re-ranked using the average deductive agreement score for every step in the proof using the validator. The score is calculated on a single step $T_{i}=(\mathbf{x}_{1},\mathbf{x}_{2}\rightarrow\mathbf{c})$ by recreating $\mathbf{c}$ using the deductive step model $\mathbf{c^{\prime}}=S_{d}(\mathbf{x}_{1},\mathbf{x}_{2})\rightarrow\mathbf{c^{\prime}}$. We then test $\mathbf{c^{\prime}}$ for entailment of the original step’s conclusion $s=entail(\mathbf{c^{\prime}},\mathbf{c}$) and taking the entailment probability as a score. Averaging these probabilities across all steps, $score=\frac{1}{n}\sum^{n}_{i=0}s_{i}$ where $n$ are the total number of steps in the proof, favors proofs with both deductive and abductive steps that verify deductively and minimizes the expected fraction of errors in the proof.

Everyday Norms: Why Not?

To evaluate our method, we need data consisting of entailment trees $T$ as shown in Figure 4. EntailmentBank Dalvi et al. (2021) is the only existing dataset suitable for this evaluation; however, it is limited to the elementary science domain and we found that step models can often elide minor steps such as synonym replacements, making many instances easy to solve.

We collect a new English-language dataset called Everyday Norms: Why Not? (ENWN) describing why an action is or isn’t appropriate given a set of circumstances and a set of assumed norms.We note that unlike Delphi Jiang et al. (2021), all of the assumptions here are made explicit in the inputs (taking your neighbor’s property without asking permission is stealing, stealing is wrong) rather than relying on the system’s priors. Our emphasis is on benchmarking the ability of systems to produce conclusions given stated premises, not trying to automate moral judgments per se Talat et al. (2021). ENWN consists of 100 entailment trees annotated by the first two authors of this paper. Each example considers a unique situation, providing an ethical judgement and its justification in the form of an entailment tree. Premise statements include both information about a situation as well as ethical norms. Intermediate steps are written to be similar in form to those in the EntailmentBank dataset, with the exception that all steps have two input statements.

Examples are given in Figure 4 and Appendix B. ENWN trees are slightly larger than EntailmentBank trees, with an average of 4.71 steps in comparison to EntailmentBank’s 4.26. Anecdotally, we note that most steps in ENWN cannot be easily elided as they do not involve premises expressing trivial identities, such as “Green is a color,” which occur often in EntailmentBank.

Experimental Setup

We evaluate our models on the premise recovery task according to the two criteria stated previously, recall of missing premises and validity. Recall of missing premises, which we refer to as coverage, is defined using our recovery scoring $E(\mathbf{x}_{m},\mathbf{x^{\prime}})\geq 0.7$. An example only has to produce one tree containing the missing premise to be counted towards the coverage metric. We use human evaluation to evaluate validity.

We evaluate on the English-language EntailmentBank Dalvi et al. (2021) test set and our new Everyday Norms: Why Not? (ENWN) dataset. To control for tree depth, our test examples are produced by slicing each full entailment tree into treelets and removing a single premise from each treelet. Slicing trees allows us to create settings of varying difficulty (deeper treelets being more difficult) and since each treelet has at least two premises we can generate many individual examples. For our evaluations in Table 1 we use a random sampling of 100 treelets for both the EntailmentBank and ENWN datasets.

We compare various models, including End-to-End (E2E), Deductive only (DG), Abductive only (AG), Abductive and Deductive (ADG), and finally our full model, Abductive and Deductive with Validation (ADGV). We now proceed to describe these models.

The first baseline we compare against is the deduction system of Bostrom et al. (2022). We will simply use this system as originally specified, applying it to the incomplete premises to see if the missing premise can be inferred through deduction alone.

Abductive Generation Only (AG)

This model only uses abductive generation. Though this can be effective for certain tree structures and small trees, it cannot generate any intermediate steps requiring forward inference as in Figure 1.

End to End (E2E)

Finally, we compare against an end-to-end model that generates a premise conditioned on a set of premises and a goal. We use T5 3B fine-tuned on an adapted EntailmentBank dataset with appropriately constructed training examples; more details are in Appendix A. Note that this model does not generate a proof and only infers the premise, which we will see can lead to reasoning shortcuts.

2 Implementation Details

Runtimes lengthen as the total number of steps increase and the total number of generations sampled increase. For the largest model (ADGV) with 50 total steps, 40 abductive generation samples per step and 10 deductive generation samples per step, examples are completed in 1 to 2 minutes on average.

Our sequence-to-sequence models are instances of T5 3B Raffel et al. (2020). Our entailment models and learned heuristic models use DeBERTa Large He et al. (2021) with 350M parameters. All models are implemented with the Hugging Face transformers library Wolf et al. (2020). Further details including fine-tuning hyperparameters are included in the appendix.

All of the $entailed(\mathbf{x},\mathbf{y})$ calls performed during the search use the same EBEntail-Active model as in Bostrom et al. (2022). We define the rightward entailment score in our work as $score=entailed(\mathbf{x}_{m}^{\prime},\mathbf{x}_{m})$. This entailment can be read as the generated missing premise entailing the actual missing premise. We empirically found this to agree best with our annotations, as discussed in Section 6.3, and used rightward for our results.

Results

As our chief goal is to infer missing premises, we begin with premise recovery (coverage) results, shown for all baselines and our best models across both datasets in Table 1. We then discuss human evaluation of both step validity (Table 4) and coverage (Table 5).

DG cannot recover any of the premises at any level of depth,Because the Forward step model requires at least 2 premise statements to perform a step, the model was not run in the D1 setting because those trees only have 1 premise. illustrating that these premises truly are unstated assumptions not derivable through forward inference.

Using deductive steps generally improves coverage (and validity).

AG is capable of producing the missing premise nearly as often (and sometimes more so) than ADG. However, because the re-ranking algorithm in Section 3.4 favors steps with high deductive agreement, ADG produces slightly higher quality proofs in general, shown in Table 2’s Score column.

Validators vastly improve quality at the cost of recall

Although using validators produces far fewer proofs in Table 1, the quality of proof trees is vastly improved in the ADGV setting. We study the statistics of these generated trees in Table 2. Because there are not actually many valid ways to recover a missing premise, lower proof counts typically indicate more reliable proofs. Shorter proofs also tend to be more consistent with those in the gold entailment trees. Score is the deductive agreement score used to rank the proofs, with higher scores indicating better validity. Finally, Premise Recall (P Recall) is the percentage of the original premises used in the proof. High Premise Recall indicates that more of the input was used to derive the missing statement which indirectly leads to better quality and indicates less hallucination.

Appendix E shows examples of successful and unsuccessful proofs from this method. These illustrate the difficulty of our dataset instances, highlighting how we need to not only chain together the correct inferences and produce the correct statement but also do so within the search budget. Exhaustive search over the space of natural language statements leads to an exponentially large fringe; however, overly heavy filtering may remove a precisely-worded intermediate conclusion needed to recover the missing premise exactly. Finding a balance is a key challenge with stronger methods.

While E2E can recover many premises, it does not construct proofs and uses shortcuts

In nearly every depth setting, the E2E model recovers a higher number of premises than our methods. However, the mechanisms that produce these generations can be unsound. Often, when abduction is performed, the level of specificity to abstract or retain is underspecified (as mentioned in Section 3). The E2E model is able to learn these levels of specificity and perform a “premise algebra” from priors in the training data that the step generation baselines cannot exploit (see examples in Appendix D). That is, the model can identify keywords that are systematically missing from examples and infer that the missing premise must use them.

Table 3 shows an experiment in which the E2E model is given a set of incomplete premises without the goal and is asked to produce the missing premises. We find that this E2E without Goal model is capable of solving 32% of the examples showing that more than half of the examples solved by the E2E model in Table 1 could have been solved using premise algebra shortcuts. In contrast, our model cannot exploit these shortcuts.

ENWN is a challenging dataset for future work

Even the “premise hacking” E2E model only achieves around 20% recovery of missing premises on the full setting. Producing a valid tree that recovers the correct premise is out of range of our current models given our computation budget. We expect scaling the sizes of our models and using improved filtering during search to prioritize the right branches may lead to improvements.

2 Human Step Validity Evaluation

Beyond coverage, we want to ensure that our models are taking sound abduction steps, which can also help evaluate whether the model is able to make valid inferences even if the missing premise is not recovered.

We collected steps in two settings: steps from the top ranking proof in cases where the missing premise was recovered (Top Proof) and steps in the search state explored at any time from any example (All). We then labeled these steps for validity. Soundness is defined as whether the abductive inference yields (1) a true new premise (2) that validates in the forward deductive inference.

The label set includes Y (valid), N (invalid), VND (“valid but not deductive”: a true premise that doesn’t result in a valid forward deduction). Only examples labeled Y are considered a valid step. Ties between valid and invalid annotations favors invalid. Agreement across the multiple labels (Cohen’s $\kappa$) was $0.48$.

As shown in Table 4, on average, using validators produces nearly twice as many valid steps while searching for a proof. Because the proofs are re-ranked once found, the gap between ADG and ADGV in the Top Proof setting is not as dramatic, but still shows a major improvement in creating sound proofs. Having valid steps in complete proofs is important for soundness, but having more valid steps anywhere in the search state demonstrates that the ADGV search explores valid branches of reasoning more often than not.

3 Human Coverage Evaluation

Our coverage numbers in Table 1 are an automatic estimate. We undertook additional human validation to ensure that these numbers are representative of actual premise recovery rates.

We sampled 100 steps that were identified as having recovered a premise. Three of the authors then annotated each step as truly recovering the missing premise based on either exhibiting mutual entailment ($\mathbf{x}_{m}^{\prime}\leftrightarrow\mathbf{x}_{m}$) or more specific premises ($\mathbf{x}_{m}^{\prime}\rightarrow\mathbf{x}_{m}$), see Figure 3 for an example. Statements that were more general but did not entail the missing premise were relatively rare and were not considered correct (although they can be valid abductive inferences in some cases), along with other unrelated or bad cases. Ties between the annotators favored the negative (the premise was not recovered); however, annotator agreement was reasonably high with Cohen’s $\kappa$ at $0.74$.

Table 5 measures the premise recovery agreement (coverage) of the ADG and ADGV systems with manual annotators. We note that the majority of premises marked as recovered by the system are valid missing premises, supporting the validity of our results in Table 1. However, we see that the validated results in ADGV tend to align better with human judgments by $14\%$; this casts the recovery results of Table 1 in a more favorable light for the ADGV system.

4 Error Analysis: ADGV

Although validation can help avoid abductive underspecification, the validation models can fail to filter invalid steps. For example, $\mathbf{x}_{a}\ =$ “A reptile does not have fur.” and $\mathbf{g}\ =$ “Animals in the taxonomic groups bird and reptile do not have fur.” combine together produce the abductive generation “Birds do not have fur.” Although this inference passes validation, if we attempt to recreate the goal through forward deduction, we would fail as information about taxonomic groups of animals is not specified. The validator thresholds could be changed to filter this, but this is a challenging case anyway as it is not obvious how to phrase an abductive generation to yield the correct result here.

Cascading errors

There is no way for ADGV to test for fallacious generations or false premises. For example, if $\mathbf{x}_{a}\ =$ “A plant is a kind of living thing.” and $\mathbf{c}\ =$ “Grass and a cow are both a kind of plant.”, $\mathbf{c}$ is a false statement, but the abductive step model can still produce a valid generation “Grass and a cow are both living things.”. However, any proof generated that includes this step would be unsound because $\mathbf{c}$ is false.

Premises that subsume their conclusions

If a premise statement $\mathbf{x}_{a}$ includes a conclusion $\mathbf{c}$, there is nothing to infer from the resulting abductive step that would be meaningful. However, the abductive heuristic can still select these steps and generate abductive inferences that bypass validation. For example, if $\mathbf{x_{a}}\ =$ “A substance is highly reflective, able to conduct electricity, and have high melting points.” and $\mathbf{c}\ =$ “The substance has high melting point.”, $\mathbf{x_{a}}$ entails $c$ on its own (as well as additional information), leading the step model to generate $\mathbf{x_{b}}\ =$ “The substance is highly reflective and able to conduct electricity.” Although $\mathbf{x_{b}}$ may be true, it is not strictly an abduction, and as an independent statement will tend to pollute the search on the next step. Preventing premises from combining with conclusions they already entail could reduce search state complexity and increase step validity, but this is left for future work.

Related work

Our work stems from well established models in the question answering domain Rajpurkar et al. (2016); Yang et al. (2018); Kwiatkowski et al. (2019). Specifically, models have often looked at either generating the correct answer or selecting statements from a set to derive an answer in a “multi-hop” manner Chen et al. (2019); Min et al. (2019); Nishida et al. (2019). Although discriminative models select evidence for their answers, there is little reasoning being exposed making it hard to detect affordances taken by the end-to-end approaches Hase and Bansal (2020); Bansal et al. (2021).

Recently, step-by-step models have been used to create entailment trees that expose a model’s reasoning down to individual deductive operations Bostrom et al. (2022); Dalvi et al. (2021); Ribeiro et al. (2022). Some with the ability to perform backward inferences have also been introduced Hong et al. (2022); Qu et al. (2022). However, these methods focus on entailing a goal rather than recovering missing evidence. Other work has explored validating step model generations Yang et al. (2022), but to our knowledge none have used abductive and deductive step models to mutually validate each other.

Chain-of-thought prompting techniques have been used to conduct step-by-step reasoning by eliciting intermediate steps from large language models (Wei et al., 2022; Creswell et al., 2022), but these have been applied to other problems and some preliminary experiments indicate that they do not immediately work for our setting. A related method has been proposed which decomposes statements into inferred premises via backward inference (Jung et al., 2022), although this approach does not simultaneously connect forward inferences from provided premises as our proposed method does.

Conclusion

In this work, we tackle the generation of missing premise statements in textual reasoning through the use of abduction. We introduce a new system capable of abductive and deductive step generation, which yields inferred missing premises while building a proof showing its reasoning. Furthermore, we propose a novel validation method that reduces hallucination and other common failure modes in end-to-end and stepwise searches. Future work can improve our system by scaling up the models used, plus using additional notions of validation as discussed in the error analysis. We believe our overall framework can be a promising foundation for future reasoning systems.

Limitations

End-to-end models are able to produce a single generation per example reducing the time complexity for sufficiently small sets of premises. Step-by-step models like our search procedure in this work are capable of handling sets of any size of premises for the search, but do increase the execution time per example, especially when using validators that require doing generation themselves. Nevertheless, validators do reduce the total time required for running a set of examples due to their ability of pruning the search space and thus removing numerous heuristic and generation calls. With better heuristics and validators it may be possible to reduce the time complexity further, but that is left for future work.

Both the EntailmentBank and ENWN dataset were written in English and capture relatively limited domains of textual reasoning. Different languages might introduce easier lexical patterns for abstraction though and could be a promising path forward. We believe ADGV and its variants should work on non-English languages, but testing this was left to future work.

ENWN draws on everyday ethical scenarios because this was a domain we found fruitful to exhibit the kind of reasoning our system can do. However, we do not follow in the steps of Delphi Jiang et al. (2021) in making any claims about its ability to make systems ethical or say anything about “values” encoded in pre-trained models. We do not support its use as part of any user-facing system at this time.

Acknowledgments

This work was supported by NSF CAREER Award IIS-2145280, the NSF Institute for Foundations of Machine Learning, ARL award W911NF-21-1-0009, a grant from Open Philanthropy, and gifts from Salesforce and Adobe. This material is also based on research that is in part supported by the Air Force Research Laboratory (AFRL), DARPA, for the KAIROS program under agreement number FA8750-19-2-1003. The views and conclusions contained herein are those of the authors and do not represent the views of DARPA or the U.S. Government. Thanks to the anonymous reviewers for their helpful feedback.

References

Appendix A Implementation Details

All experiments were conducted using Hugging Face transformers version 4.20.0.

For all experiments in this paper a set of 3 Quadro 8000 GPUs with 48GB of RAM were used.

Model weights from Bostrom et al. (2022) were used for the Deductive step model, Learned (Goal)+PPM heuristic model and the entailment model.

Default hyperparameters from HuggingFace are used if not otherwise specified for all Step models and the End-to-End model. No hyperparameters sweeps were conducted on these:

Appendix B Everyday Norms: Why Not? Examples

Appendix C Premise Recovery Generation Examples

Appendix D E2E no goal premise recovery

In Table 10 we show three examples of the ablated model E2E w/o goal correctly generating the missing premise despite being given insufficient information to do so logically. This behavior is problematic as correctly identifying which premise to generate is a vast search space without the goal to direct the model — clearly indicating that the E2E model has learned shortcuts in the data set and is taking advantage of them. Ideally, models would make sound inferences without using spurious patterns from the training dataset to create generations, which is exactly what our step models are designed to do.

Appendix E Example Proofs and Failed Searches

We include multiple example proofs generated by our models from Table 1 at depth = all. Each figure visualizes proofs from a specific model (ADGV on Figure 6 and ADG on Figure 7) and shows two examples from the ENWN dataset on the top and one example from the EntailmentBank dataset on the bottom. Furthermore, we show 8 examples of where the ADGV model failed to produce a proof with a caption explaining where the errors occurred. The first 7 failed search examples are from ENWN and the last is from EntailmentBank.