  Reasoning over natural language is a challenging problem in NLP. In this
work, we focus on proof generation: Given a hypothesis and a set of supporting
facts, the model generates a proof tree indicating how to derive the hypothesis
from supporting facts. Compared to generating the entire proof in one shot,
stepwise generation can better exploit the compositionality and generalize to
longer proofs but has achieved limited success on real-world data. Existing
stepwise methods struggle to generate proof steps that are both logically valid
and relevant to the hypothesis. Instead, they tend to hallucinate invalid steps
given the hypothesis. 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 the proof steps to prevent
hallucination. 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. Specifically, it
improves the correctness of predicted proofs from 27.7% to 33.3% in the
distractor setting of EntailmentBank, demonstrating the effectiveness of
NLProofS in generating challenging human-authored proofs.
