Natural Language Deduction with Incomplete Information

1 Introduction

• Abduction generates an explanation from a premise and conclusion, but its freeform setting has a large space of valid outputs.Prior work has framed abduction as multiple choice, although freeform generation is the setting faced by real-world explainable reasoning systems.Source: §1 · p. 1
• Existing entailment-tree methods are more transparent than end-to-end discriminative models but require all necessary premises up front and lack abduction.These methods represent deductive inferences in natural language [Dalvi et al., 2021; Bostrom et al., 2022; Yang and Deng, 2021; Hong et al., 2022].Source: §1 · p. 2
• ADGV searches forward from incomplete premises and backward from a goal, validating inferences as it builds a proof and recovers missing evidence.Its search interleaves deductive and abductive steps.Source: §1 · p. 2
• The approach evaluates missing-premise recovery on EntailmentBank and Everyday Norms: Why Not?, measuring both premise coverage and step validity.The introduction reports high validity but says coverage still has significant headroom.Source: §1 · p. 2
• ADGV combines abductive and deductive step generation with validation techniques intended to improve step validity.The paper also introduces the missing-premise recovery task and the Everyday Norms: Why Not? dataset.Source: §1 · p. 2

2 Problem Description

• The task removes one evidence item xm from a tree and requires recovering it while proving goal g from the remaining evidence.Existing deduction systems operating over stated premises cannot reach the goal in this underspecified setting [Dalvi et al., 2021; Bostrom et al., 2022].Source: §2 · p. 2
• A trivial solution—assuming xm equals the goal—produces a vacuous proof, and the authors note that no easy first-order rule identifies atomic premises.The text gives examples ranging from low-level definitions to complex process descriptions.Source: §2 · p. 2
• Recovery is evaluated by whether a generated premise is logically equivalent to xm, while human ratings assess the validity of its proof tree.The search iteratively unrolls the goal into simpler statements while attempting to recover the specific missing premise.Source: §2 · p. 3

3 Methods

• The deductive step model maps premises to useful conclusions, while the abductive step model uses one premise and a conclusion to hypothesize missing information.The paper uses two premises for deduction and one premise plus a conclusion for abduction.Source: §3 · p. 3

3.1 Step Models

• The abductive model is a pretrained language model specialized to map a conclusion and one premise to a hypothesized missing premise.It is trained by converting each two-input EntailmentBank step into abductive examples, ablating each input in turn.Source: §3.1 · p. 3

3.2 Search

• ADGV interleaves deductive and abductive fringes, sampling multiple generations and pruning branches that fail validation.Round-trip validators check whether generations from one step type agree when tested through the other step type.Source: §3.2 · p. 4
• A learned abductive heuristic prioritizes search using positive examples formed from step inputs paired with their conclusion and negative examples from unrelated statements.The heuristic is a DeBERTa-v3 Large model fine-tuned on those positive and negative samples.Source: §3.2 · p. 4

3.3 Premise Recovery Scoring

• Recovered premises are scored with the harmonic mean of ROUGE-1 similarity and entailment, then filtered by a threshold.Each recovered premise is associated with a derivation that entails the goal.Source: §3.3 · p. 5

3.4 Re-Ranking Proofs

• Proofs are reranked by average deductive-agreement scores across their steps, favoring proofs whose steps verify deductively.Each step is recreated with the deductive model and scored for entailment of its original conclusion.Source: §3.4 · p. 5

• EntailmentBank is limited to elementary science, and step models can often elide minor steps, making many instances easy to solve.Source: §4 · p. 5
• ENWN describes why an action is or is not appropriate given circumstances and assumed norms.Source: §4 · p. 5
• Figure 4 marks premises in light blue, gold intermediate steps in dark blue, and the goal statement in green.The final light-blue premise is the gold missing premise; dark-blue steps are used during training but hidden during inference.Source: Figure 4 · p. 5
• ENWN contains 100 author-annotated entailment trees, each presenting a unique situation, an ethical judgment, and its justification.Premises combine situational information with ethical norms; each intermediate step takes two input statements.Source: §4 · p. 5
• ENWN trees average 4.71 steps, compared with 4.26 for EntailmentBank, and most ENWN steps cannot be easily elided as trivial identities.Source: §4 · p. 5

5 Experimental Setup

• Coverage counts an example when at least one generated tree contains a recovered premise scoring E(xm, x′) ≥ 0.7; humans evaluate step validity.Source: §5 · p. 5
• Evaluation uses 100 randomly sampled treelets per dataset, sliced from EntailmentBank and ENWN trees with one premise removed to vary difficulty by depth.Source: §5 · p. 6

5.1 Baselines

• The baselines include deduction-only DG, abduction-only AG, and T5 3B end-to-end generation, which predicts a premise without generating a proof.AG cannot generate intermediate steps requiring forward inference, while E2E can take reasoning shortcuts.Source: §5.1 · p. 6

5.2 Implementation Details

• Two-fringe systems receive backward budgets of 2, 4, 8, 16, or 25 steps by depth, with matching forward budgets; abductive steps sample 40 generations and deductive steps 10.The additional forward budget increases wall-clock time; ADGV examples with 50 total steps average 1 to 2 minutes.Source: §5.2 · p. 6
• Premise recovery uses rightward entailment: the generated missing premise must entail the actual missing premise, a score found to agree best with annotations.Source: §5.2 · p. 6

6.1 Coverage Results

• DG recovers no missing premises at any depth, while adding deductive steps generally improves coverage and validity.These results support the need for abductive generation alongside deduction.Source: §6.1 · p. 6
• Across both datasets, ADGV produces fewer proofs but higher-scoring proofs that use more original premises than ADG and AG.The reported trade-off is fewer proofs in exchange for higher scores and greater use of the input premises.Source: Table 2 · p. 7, §6.1 · p. 7
• AG produces missing premises nearly as often as ADG, but ADG generally yields higher-quality proofs because reranking favors deductive agreement.The comparison concerns recovery frequency and proof quality, respectively.Source: §6.1 · p. 7
• The E2E model recovers more premises in nearly every depth setting, but it does not construct proofs and can exploit training-data shortcuts.An E2E variant given no goal still recovers premises in 32% of examples, indicating that some cases can be solved through premise-algebra shortcuts.Source: §6.1 · pp. 7–8, Table 3 · p. 7
• On ENWN, even the premise-hacking E2E model recovers only around 20% of missing premises in the full setting, and producing a valid tree is beyond current computation budgets.Exhaustive search creates an exponentially large fringe, while heavy filtering can remove an intermediate conclusion needed for exact recovery.Source: §6.1 · pp. 7–8

6.2 Human Step Validity Evaluation

• Validators yield nearly twice as many valid steps on average during search; the gap is smaller for top proofs after reranking but still shows a major improvement.The manual evaluation sampled 200 reasoning steps across ADG and ADGV in Top Proof and All settings.Source: §6.2 · p. 8, Table 4 · p. 8

6.3 Human Coverage Evaluation

• Most system-identified recoveries were valid, and ADGV aligned with human judgments 14% better than ADG.The human coverage evaluation supports the automatic recovery results and finds better alignment for ADGV.Source: §6.3 · p. 8, Table 5 · p. 9

6.4 Error Analysis: ADGV

• A potentially unhelpful abductive premise can be true yet fail to be a strict abduction, polluting later search; preventing already-entailed premise–conclusion combinations is left for future work.The authors suggest this could reduce search-state complexity and increase step validity.Source: §6.4 · p. 9

7 Related work

• Question-answering systems generate answers or select evidence for multi-hop reasoning, while discriminative evidence selection exposes little reasoning.The cited work notes that limited exposed reasoning makes it difficult to detect affordances taken by end-to-end approaches.Source: §7 · p. 9
• Entailment-tree methods expose individual deductive operations, but focus on entailing a goal rather than recovering missing evidence.Some methods support backward inference, and other work validates generated steps, but the authors know of no method using abductive and deductive step models to mutually validate each other.Source: §7 · p. 9
• Chain-of-thought prompting elicits intermediate steps, but preliminary experiments indicate it does not immediately work for this setting.A backward-inference method decomposes statements into inferred premises but does not simultaneously connect forward inferences from provided premises.Source: §7 · p. 9

8 Conclusion

• The paper uses abduction to generate missing premise statements in textual reasoning.ADGV combines abductive and deductive step generation to infer missing premises while building a proof that shows its reasoning.Source: §8 · p. 9
• The proposed validation method reduces hallucination and other common failure modes in end-to-end and stepwise searches.The framework is presented as a promising foundation for future reasoning systems.Source: §8 · pp. 9–10
• Future work may scale the models and add further validation notions discussed in the error analysis.The authors also suggest the framework as a foundation for future reasoning systems.Source: §8 · p. 10

9 Limitations

• Step-by-step search handles premise sets of any size, but increases per-example execution time, especially when validators also generate text.Validators can nevertheless reduce total runtime across examples by pruning the search space and removing heuristic and generation calls; further time-complexity improvements are left for future work.Source: §9 · p. 10
• Both datasets are English and cover relatively limited domains of textual reasoning; non-English performance remains untested.The authors believe ADGV and its variants should work in other languages, but leave testing this to future work.Source: §9 · p. 10
• ENWN's everyday ethical scenarios do not support claims about ethical system capabilities or values encoded in pretrained models.The authors do not support using the dataset or system as part of a user-facing system at this time.Source: §9 · p. 10

A Implementation Details

• Experiments used Hugging Face Transformers 4.20.0 and three Quadro 8000 GPUs with 48GB of RAM.Source: A Implementation Details · p. 13
• Deductive step, learned (Goal)+PPM heuristic, and entailment models used weights from Bostrom et al. (2022).Source: A Implementation Details · p. 13
• Step models and the end-to-end model used Hugging Face defaults unless otherwise specified; no hyperparameter sweeps were conducted.Source: A Implementation Details · p. 13
• Tables 7 and 8 are labeled for the abductive step model and abductive learned-heuristic fine-tuning, respectively.Source: Table 7 · p. 13, Table 8 · p. 13

B Everyday Norms: Why Not? Examples

• ENWN example trees distinguish given premises, intermediate deductive steps, goals, and gold missing premises by box style and color; each intermediate step has arity two.Source: Figure 5 · p. 15

D E2E no goal premise recovery

• The no-goal E2E model generates missing premises from insufficient information, indicating it has learned and exploits dataset shortcuts.The authors contrast this behavior with step models designed to make sound inferences without spurious training patterns.Source: D E2E no goal premise recovery · p. 16
• Table 9 samples 11 abductive steps across varying-depth experiments, showing each model’s best generation and its E(x′, x) score against the gold premise.The table’s depth column corresponds to the depth settings in Table 1.Source: Table 9 · p. 17
• In two of Table 10’s three examples, the no-goal E2E model computes the missing premise word for word.The table presents cases where the model is given only a subset of premises and no goal.Source: Table 10 · p. 18

E Example Proofs and Failed Searches

• Figures 6–7 show successful ADG proofs from the Depth = all experiment: generated premises have blue stripes and orange x′, while gold missing premise xm has blue stripes and green text.The gold missing premise is never incorporated because the step models are being tested on whether they can regenerate it.Source: Figure 6 · p. 20, Figure 7 · p. 21
• Some searches fail because a fringe omits useful premises or the deductive and abductive fringes do not combine.Examples include ADGV repeatedly combining only a subset of premises and a heuristic ranking that misses useful cross-fringe combinations.Source: Figure 8 · p. 22, Figure 9 · p. 23, Figure 14 · p. 28
• Near-correct abductive generations can be false negatives: one is judged too specific, while another scores 0.57, below the entailment threshold.The examples concern ENWN searches and compare generated premises with the intended missing premises.Source: Figure 10 · p. 24, Figure 11 · p. 25
• A technically valid abductive generation can still be wrong for the proof goal, while the heuristic or validators may fail to select or remove it.Figure 12’s example calls for combining a premise about Cindy’s team with an earlier abductive generation instead.Source: Figure 12 · p. 26
• Most failed searches have large trees; repeated rephrasings can deepen proofs, and the Consanguinity filter addresses this pattern.The authors report that slight generation tweaks can improve step recall because entailment scores and heuristics favor particular phrasings.Source: E Example Proofs and Failed Searches · p. 19, Figure 13 · p. 27