Dispersed Hierarchical Attention Network for Machine Translation and Language Understanding on Long Documents with Linear Complexity (2023)

Abstract: Transformers, being the forefront of Natural Language Processing and a pioneer in the recent developments, we tweak the very fundamentals of the giant Deep Learning model in this paper. For long documents, the conventional Full SelfAttention exceeds the compute power and the memory requirement as it scales quadratically. Instead, if we use a Local Self-Attention using a sliding window, we lose the global context present in the input document which can impact the performance of the task in hand. For long documents (ranging from 500 to 16K tokens), the proposed Dispersed Hierarchical Attention component captures the local context using a sliding window and the global context using a linearlyscaled dispersion approach. This achieves O(N) linear complexity, where N is the length of the input sequence or document.

## introduction due to the advent of transformers, the technological world, especially in the field of natural language processing has grown by leaps and bounds. the impact spans from the gpt @xcite , @xcite , @xcite , @xcite models that have repeatedly made headlines in the main stream media to github's copilot ( https://copilot.github.com ). though it is said that the transformers model is a culmination of many ideas such as transfer learning, stacked neural networks, the basic fundamental concept that revolutionized the ideology of transformers is definitely the attention mechanism @xcite . let us now look at the concept of attention mechanism using a concrete example of abstractive text summarization. earlier, the task of abstractive text summarization @xcite was achieved using the encoder -decoder framework @xcite . it involves an encoder stack which encodes the entire text document to be summarized into a numerical representation called the last hidden state. taking this as input, the summary of the input text document is given as output by the decoder. for the task at hand, it is nearly impossible for the last hidden state to contain all the important information said in the given input document. and since the last hidden state is the only piece of information that the decoder receives, the entire task in hand is compromised. to eradicate the shortcomings of the information bottleneck which produces sub-optimal results, at every stage, the encoder generates a hidden state, mitigating the loss of important information. in the process of overcoming the information bottleneck, we end up moving from the frying pan into the fire. it is realized that there is information overload by creating a huge input corpus for the decoder while using all the encoder-generated states simultaneously. therefore, there is a need for a mechanism to prioritize the encoder states which must be considered and given more attention by the decoder. here is a preview. this paper aims at 1) elaborating extensively on the formulation of different attention mechanisms 2) proposing a new variation of attention mechanism 3) discussing where the proposed attention mechanism can be used as an application 4) evaluating the changes in complexity which in turn leads to better performance. ## variation from the plethora of attention mechanisms @xcite that have been explained in the previous sections, we find a commonality. if an attention mechanism tries to comprehend the entire input document using the full (global) self-attention, the computational requirements and the memory requirements increase in a quadratic manner. while processing long documents, the above stated methodology is rendered incompatible. acting upon this, if we downsize the attention mechanism to sliding window or dilated sliding window, though the complexity and the memory usage come down drastically, the global context of the entire input document is lost and only a local context is captured. here is a variation in the attention component which tries to comprehend the global context of the entire document along with the local context. intuitively, the neighboring tokens contain more weightage for any given token and therefore ideally these said tokens have to be given more attention. as we move away from the token, the importance of the respective tokens which are not in close proximity decreases. this intuition forms the theoretical basis of the proposed attention component -dispersed hierarchical attention. dispersed hierarchical attention is a combination of sliding window attention along with a linearlyscaled dispersion on either sides of the token embedding. the sliding window contributes to the local context and the linearly-scaled dispersion considers token with reducing importance with respect to the decrease in proximity. this methodology still manages to capture the global context to some extent as well. from figure 8 , though it may not be evident for a small scope of @xmath0, the dispersion occurs in a linear manner as we lose proximity with the corresponding token embedding thus reducing the quadratic complexity. taking the values from the figure shown above, we calculate the total number of attention scores to be calculated from the attention matrix by substituting the values in equation ( 3 ) and the total number of attention score is found be 94. the total number of attention scores while using the dispersed hierarchical attention can be found by adding the number of attention scores present in the sliding window from equation ( 3 ) and the number of attention scores that are given as output from algorithm 1. we can also mathematically find the number of attention scores via the steps given below. if you notice the attention matrix of the dispersed hierarchical attention mechanism, there is an innate series of number of tokens to either side of the token excluding the sliding window. equation ( 4 ) will give us the value of x which denotes till which number the above series will go on given the sequence length, n and window size, w. basically, all the numbers in the series must be summed up to find the number of attention scores to be calculated on either the lower triangular matrix or the upper triangular matrix of the attention matrix. one important point that has to be noted is that, based on the number of input tokens, n, there is a possibility that the series is never fully complete and therefore in that case a part of the last entry has to be removed and for that we do the further calculations given below. the remainder is a (negative) number that can be subtracted from sx. therefore, the final refined formula for finding the total number of attention scores, attdispersed is given below via equation ( 10 ) by combining the equations ( 3 ), ( 8 ) and ( 9 ) ## application in the previous section, the proposed variation for the attention component present in the transformer model was discussed. it also provided us with the formulation of the total number of attention scores for any given sequence of input length, n and window size, w. the next step is to create a function (algorithm 2) for the dispersed hierarchical attention mechanism so that it can be replaced with the existing attention functions and can be imbibed in a transformer. the algorithm divides the sequence into local windows (sliding window) and calculates the attention scores within those windows to capture the local context. to capture the global context, attention scores for the dispersed tokens to the right and left of the local window are calculated. the gap sequence defined in algorithm 2 spans from 2 to 180 in order to accommodate the input sequence length up to 16470 tokens (equation ( 11 )). since, the longformer @xcite transformer can take documents containing tokens up to 16384, the specified gap sequence is the maximum that the proposed attention can span. ## evaluation to evaluate the performance of the proposed attention, we use a comparative approach ( ## conclusion and future work this novel work mainly focuses on reducing the complexity of the attention mechanism used in the transformer model. in the proposed attention mechanism, selective tokens which are linearly dispersed from the query are used as keys. this addresses the problem of considering the local and global context associated with large input documents while potentially lowering computing and memory costs. the solution proposed brings the understanding of both the local and global context to middle ground. in future, the proposed dispersed hierarchical attention mechanism can be integrated with a series of transformer models replacing the existing attention mechanisms implemented and could be tested on the efficiency improved in performing various nlp tasks such as text summarization, question answering, sentiment analysis and machine translation.