Natural Language Deduction through Search over Statement Compositions

Our step models are instances of the T5 pre-trained sequence-to-sequence model Raffel et al. (2020) fine-tuned on a combination of deduction step datasets from prior work Dalvi et al. (2021); 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$.

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}\dots x_{m}\},\ g)\rightarrow\mathbb{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.

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.

We consider several potential realizations of the heuristic function $h$:

In order to determine when the search has succeeded, we need a module to judge the 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.

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.

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.

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.

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 end-to-end on this dataset.

We compare against an End-to-end T5 model that we train following the EntailmentWriter paradigm Dalvi et al. (2021). 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, Dalvi et al. (2021) fine-tune T5-11b (Raffel et al., 2020); we replicate their training setup using T5-3b instead for parity with our other experiments.

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 $\frac{1}{L}\sum_{i=1}^{L}\log p_{\theta}(t_{i}\mid t_{1}\dots t_{i-1})$. 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 $\in\{0,1\}$ based on this quantity. We refer to this discriminative setup as End-to-end (Intrinsic).

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 post-hoc explanations of the decision.

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 $\alpha=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.

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.

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 $\alpha$. For the End-to-end (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(\texttt{T})/(p(\texttt{T})+p(\texttt{F}))$, the score assigned to the “valid” flag token by the model out the two possible validity flags.

In addition to evaluating end-to-end performance through the above tasks, we would also like to understand the internal consistency of generated 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.

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.

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-to-end 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.

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}\dots T_{|D|}\}$ for validity rate $v$ can be computed as $\frac{1}{|D|}\sum_{i=1}^{|D|}v^{|T_{i}|}$. At a step validity rate of 82% we should expect $\sim$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 $\sim$35% of its trees to be fully valid.

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.

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; macro-averaged inter-annotator F1 is 0.83 and Cohen’s $\kappa$ 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.

Although our step model cannot hallucinate based on the hypothesis, it can still fail to produce valid intermediate steps due to other challenges.

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.

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.

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.

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.

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.

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.

Future work could expand the training data of our NLI model to account for the subjectivity of NLI judgments Pavlick and Kwiatkowski (2019); Chen et al. (2020); Nie et al. (2020), particularly by modifying our data collection procedure Zhang et al. (2021).