  Human language is known to exhibit a nested, hierarchical structure, allowing
us to form complex sentences out of smaller pieces. However, many
state-of-the-art neural networks models such as Transformers have no explicit
hierarchical structure in its architecture -- that is, they don't have an
inductive bias toward hierarchical structure. Additionally, Transformers are
known to perform poorly on compositional generalization tasks which require
such structures. In this paper, we introduce Treeformer, a general-purpose
encoder module inspired by the CKY algorithm which learns a composition
operator and pooling function to construct hierarchical encodings for phrases
and sentences. Our extensive experiments demonstrate the benefits of
incorporating hierarchical structure into the Transformer and show significant
improvements in compositional generalization as well as in downstream tasks
such as machine translation, abstractive summarization, and various natural
language understanding tasks.
