ETC : Encoding Long and Structured Inputs in Transformers (2020)

Abstract: Transformer models have advanced the state of the art in many Natural Language Processing (NLP) tasks. In this paper, we present a new Transformer architecture, “Extended Transformer Construction” (ETC), that addresses two key challenges of standard Transformer architectures, namely scaling input length and encoding structured inputs. To scale attention to longer inputs, we introduce a novel global-local attention mechanism between global tokens and regular input tokens. We also show that combining global-local attention with relative position encodings and a “Contrastive Predictive Coding” (CPC) pre-training objective allows ETC to encode structured inputs. We achieve state-of-the-art results on four natural language datasets requiring long and/or structured inputs.

## introduction models based on transformers @xcite , such as bert @xcite , or other variants @xcite @xcite have yielded state-of-the-art results in many nlp tasks such as language modeling @xcite @xcite , question answering @xcite , and summarization @xcite . we present the extended transformer construction (etc) architecture foot_0 , targeting two limitations of the original models: (1) scaling input length, (2) encoding structured inputs. the computational and memory complexity of attention in the original transformer scales quadratically with the input length, typically limiting input length to around 512 tokens. while 512 might be enough for some tasks (e.g., co-reference resolution seems to benefit from even smaller input lengths @xcite ), this is problematic in others. consider question answering (qa) tasks that require reasoning across multiple documents (e.g., the hotpotqa dataset @xcite ) all of which must simultaneously fit in the model input. other examples are summarization, or qa on long documents. many approaches have been proposed to address this, like hierarchical processing @xcite , sparse attention @xcite , and segment-level recurrence @xcite . a second limitation is that few models focus on structured inputs, by which we refer to any underlying graph or hierarchical structure among the input tokens. although etc can encode more general graph structure, in this work we focus on representing hierarchical structure in nlp tasks, not usually modeled by transformer models. for example, text is organized into sentences and paragraphs, and while these have a sequential order, different input documents might not hold any order between them (e.g., the hotpotqa dataset). additionally, web text contains markup and is laid out using a dom tree, giving additional structure. we show etc can represent these and other types of structure, like linking different entity mentions. to address these challenges, we present a novel attention mechanism called global-local attention, which divides the input into two sequences (which we call the global input and the long input). this mechanism introduces local sparsity to reduce the quadratic scaling of the attention mechanism. when this is coupled with relative position encodings @xcite , it allows for handling structured inputs in a natural way. additionally, unlike previous transformer extensions, etc can be initialized from existing pre-trained standard bert models (which together with a gpu/tpufriendly implementation, allows for efficient model training) 2 . our results show that initializing from roberta @xcite significantly improves performance. finally, we show that by adding a pre-training contrastive predictive coding (cpc) task @xcite , performance improves even further for tasks where structure is important, as cpc plays the role of a masked language model (mlm) task, but at a sentence level of granularity. we report experiments on four datasets: natural questions (nq) @xcite , hot-potqa @xcite , wikihop @xcite , and openkp (part of ms marco) @xcite , which have long and/or structured inputs. we set a new state of the art in all of them. moreover, although in this paper we strictly focus on etc, in a related model called bigbird @xcite , we experimented with an alternative set of ideas to handle long inputs and its extensions to a decoder for text generation. the focus of bigbird is on the idea of adding random sparse attention patterns to global-local attention, and on showing under which conditions models like bigbird/etc are universal approximators of sequence functions and are turing complete. while the key ideas and techniques required to achieve the state-of-the-art results mentioned above for qa tasks are the focus of this paper, the reader is referred to the bigbird work for a joint evaluation of etc (referred to as bigbird-etc in that work) and the idea of random sparse attention patterns. ## background many variants of the original transformer model @xcite have been proposed for scaling up training @xcite , the internal representation (albert, @xcite , or both (t5, @xcite , outperforming bert @xcite in tasks such as glue @xcite , squad @xcite or race @xcite . however, these models typically limit inputs to @xmath0. we classify prior approaches to scale up attention into four categories: sparse attention, recurrence, hierarchical mechanisms, and compressed attention. sparse attention involves limiting each token to attend to a subset of the other tokens. for example, the sparse transformer @xcite used predefined attention patterns for both text and image generation. they showed that attending only a new model developed concurrently to etc, which also allows initialization from bert/roberta. to previous pixels in the same row or column was enough to generate high quality images, while keeping attention cost at o(n √ n). in the adaptive attention span transformer @xcite each attention head is associated with a decaying learnable masking function, which limits the number of tokens it can attend to. they show that lower layers learn to use short attention spans, and only in higher layers are attention spans longer. sparse attention has also been used to increase the interpretability of attention heads by allowing attention to assign exactly zero weight to certain input tokens @xcite . the reformer @xcite ) model finds the nearest neighbors of the attention query (those input tokens that would result in the highest attention weights) using locality sensing hashing @xcite and only uses those for attention. this reduces attention cost to o(n log(n)). the routing transformer @xcite learns dynamic sparse attention patterns using online k-means, reducing complexity to o(n 1.5 ). finally, the most related approach to the work presented in this paper is longformer (beltagy et al., 2020), developed concurrently to etc, and which features a very similar global-local attention mechanism as etc's but does not directly encode graph or hierarchical structure (more detailed comparison in section 3). recurrence incorporates elements of recurrent neural networks into transformer models to lengthen their attention span. transformer-xl @xcite takes this approach, dividing the input sequence into segments and then processing these segments one at a time. at each layer, the model attends to the layer immediately below for both the current and previous input segments. the effect is that layer k is influenced by the current segment and the k -1 previous segments, as shown in the top-right of figure 1 . in hierarchical mechanisms the input sequence is split into blocks that are ingested independently to produce summary embeddings that represent the whole block. then, separate layers ingest the concatenation of these embeddings. for example, hibert @xcite uses this idea at the sentence level for extractive summarization (illustrated in the bottom-left of figure 1 ). hierarchical attention in transformers has also been applied to other nlp tasks such as neural machine translation @xcite . moreover, notice that this idea of processing the input hierarchically compressed attention takes the idea of hierarchical attention one step further by selectively compressing certain parts of the input. the bp-transformer @xcite model builds a binary partitioning tree over the input, and only lets the model attend to the leaves (the raw tokens) for nearby tokens, and higher nodes in the tree (summaries of groups of tokens) as tokens grow more distant (see figure 1 , middle top). other ideas include memory compressed attention @xcite where groups of k tokens are compressed via a convolution filter before they are attended to, and the star transformer @xcite , where each token can attend only to its immediate left/right neighbors and to a separate special auxiliary token that represents a summary of the whole input (see figure 1 , left). the compressive transformer (rae et al., 2019) integrates this idea into transformer-xl by compressing tokens in the input that are far away. the model benefits from detailed attention to nearby tokens, while using summarized information for more distant tokens (see figure 1 , lower right). ## extended transformer construction our model follows the original transformer architecture @xcite , with key modifi-cations to tackle long and structured inputs: relative position encoding, global-local attention, and a cpc pre-training task, explained below. in this paper, we consider only the encoder side of the transformer, and leave the decoder for future work. ## empirical evaluation this section focuses on evaluating our two main contributions: (1) long inputs, and (2) structure in text inputs, as well as initialization from existing bert models. we chose four datasets ( hotpotqa @xcite is a question answering dataset where the goal is to combine evidence from multiple contexts. we use the distractor setting, where 10 paragraphs are provided: two of them contain useful information to answer the question, and the rest are distractors. the task is both to answer the question, and also to identify the supporting facts that are relevant to answer the questions (at a sentence granularity). wikihop @xcite is similar in structure to hotpotqa. the contexts correspond to portions of wikipedia articles, and the goal is to answer about properties of an entity that cannot be found in the entity's article. each instance contains a query, a collection of candidate answers, and a collection of contexts from which to obtain information to select among the candidate answers. openkp @xcite is a keyphrase extraction dataset. each document contains up to 3 short keyphrases to be identified. we selected this dataset as the input is not flat text sequences, but websites, including the hierarchical and spatial relations between the different dom elements on the website, as well as other visual properties. ## conclusions this paper introduced the extended transformer construction (etc), an architecture designed to (1) scale up the input length (linearly with input), and (2) encode structured inputs. etc allows lifting weights from existing bert models, improving results significantly. the key ideas are a new globallocal attention mechanism, coupled with relative position encodings and a cpc pre-training task. we showed that significant gains can be obtained thanks to increased input sequence length. the ability to represent dataset structure in etc further improves the model quality. we hypothesize that cpc helps the model train the usage of the higherlevel global input summary tokens, as cpc plays a role akin to mlm, but at the global input level. notice that although our datasets contain a limited amount of structure (compared to graph datasets), our experiments show that etc was able to exploit this existing structure. as future work, we would like to investigate complementary attention mechanisms like those of reformer @xcite or routing transformer @xcite , push scalability with ideas like those from revnet @xcite , and study the performance of etc in datasets with even richer structure. dius r. for example, a q takes a dot product with d k , e k and f k , but this is easy to simply mask out, yielding the same sliding window local attention result. in this way, the blocking mechanism saves memory at the expense of some extra compute. the values are also divided into the same blocks as the keys (concatenating 3 at a time), and standard scaled dot product attention is applied independently for each row in the table below, where keys have been truncated for brevity: