Generating Natural Language Proofs with Verifier-Guided Search
Deductive reasoning (drawing conclusions from assumptions) is a challenging
problem in NLP. In this work, we focus on proof generation: given a hypothesis
and a set of supporting facts in natural language, the model generates a proof
tree indicating how to deduce the hypothesis from supporting facts. Instead of
generating the entire proof in one shot, prior work has demonstrated the
promise of stepwise generation but achieved limited success on real-world data.
Existing stepwise methods struggle to generate proof steps that are both valid
and relevant. In this paper, we present a novel stepwise method NLProofS
(Natural Language Proof Search), which learns to generate relevant steps
conditioning on the hypothesis. At the core of our approach, we train an
independent verifier to check the validity of proof steps. Instead of
generating steps greedily, we search for proofs maximizing a global proof score
judged by the verifier. NLProofS achieves state-of-the-art performance on
EntailmentBank and RuleTaker. For example, it improves the percentage of
correctly predicted proofs from 20.9% to 33.3% in the distractor setting of
EntailmentBank. This is the first time stepwise methods have led to better
generation of challenging human-authored proofs.