Bi-Directional Block Self-Attention for Fast and Memory-Efficient Sequence Modeling

Tao Shen, Tianyi Zhou, Guodong Long, Jing Jiang, Chengqi Zhang

Introduction

In Natural Language Processing (NLP), sequence modeling is typically dominated by three architectural paradigms: Recurrent Neural Networks (RNNs), Convolutional Neural Networks (CNNs), and Self-Attention Networks (SANs). While RNNs excel at capturing long-range dependencies, their sequential nature makes them slow and difficult to parallelize. CNNs are fast but often fail to connect distant words effectively. SANs have emerged as the gold standard for capturing global dependencies through parallel computation; however, they suffer from a significant "memory explosion" because their memory usage grows quadratically ($O(n^2)$) with sequence length.

Bi-directional Block Self-Attention (Bi-BloSAN) is a novel framework designed to resolve this trilemma. It provides a model that is as parallelizable as a SAN, as memory-efficient as an RNN, and capable of capturing both local and global context without the prohibitive computational costs of standard attention mechanisms.

Methodology

The core innovation of Bi-BloSAN is its hierarchical approach to attention. Instead of calculating attention for every possible pair of words in a long sequence, the model splits the sequence into small, equal-sized blocks and applies a two-tier attention mechanism:

  1. Intra-block SAN: The model first computes self-attention within each individual block to capture local context and fine-grained relationships between neighboring words.
  2. Inter-block SAN: Following the local pass, the model computes attention between the blocks themselves. This allows the network to capture long-range, global dependencies across the entire sequence.
  3. Bi-directionality: To capture temporal order—ensuring the model understands the difference between "dog bites man" and "man bites dog"—the authors utilize forward and backward masks. This enables the model to look in both directions without the need for a recurrent loop.
  4. Feature-level Attention: Unlike "vanilla" attention that assigns a single scalar score to a word, Bi-BloSAN employs multi-dimensional attention. This allows the model to focus on specific features of a word's embedding that may be relevant in different contexts.
  5. Context Fusion Gate: A gating mechanism, inspired by the gates in LSTMs, is used to intelligently merge the original word embeddings with the newly extracted local and global features.

Efficiency and Complexity

A key contribution of this work is the mathematical optimization of memory usage. By breaking the sequence into blocks of size $r$, the memory complexity is reduced from $O(n^2)$ to approximately $O(n \cdot r)$. The authors demonstrate that the optimal block length to minimize memory consumption can be calculated as $r = \sqrt[3]{2n}$. This optimization allows Bi-BloSAN to remain stable on long sequences where standard directional self-attention (DiSAN) would typically fail due to hardware memory limits.

Empirical Results

The authors evaluated Bi-BloSAN across nine benchmark datasets, including Natural Language Inference (SNLI), Reading Comprehension (SQuAD), and various sentence classification tasks (SST, TREC, CR, etc.).

  • Performance: On the SNLI dataset, Bi-BloSAN achieved an accuracy of 85.7%, outperforming Bi-LSTMs (85.0%) and matching the performance of more computationally expensive attention models.
  • Speed: Bi-BloSAN demonstrated significant efficiency gains, running 3x to 4x faster than RNN-based models like Bi-LSTM and Bi-GRU during both training and inference.
  • Robustness: On the SQuAD reading comprehension task, Bi-BloSAN significantly outperformed Multi-head attention and CNNs, proving its effectiveness in complex reasoning tasks that require both local and global understanding.
  • Ablation Studies: The studies confirmed that both local (intra-block) and global (inter-block) representations are vital; removing either component resulted in a measurable drop in accuracy.

Conclusion

Bi-BloSAN represents a significant step toward hardware-friendly NLP. By removing the necessity for recurrence while taming the quadratic memory costs of self-attention, the framework provides a scalable solution for long-form text modeling. While the model uses more memory than simple multiplicative (dot-product) attention, the authors argue that the increased expressiveness of additive, multi-dimensional attention justifies the trade-off. Future research may explore applying this block-based structure to document-level modeling or integrating it into Transformer-style architectures for machine translation.

Summary updated

Abstract

Recurrent neural networks (RNN), convolutional neural networks (CNN) and self-attention networks (SAN) are commonly used to produce context-aware representations. RNN can capture long-range dependency but is hard to parallelize and not time-efficient. CNN focuses on local dependency but does not perform well on some tasks. SAN can model both such dependencies via highly parallelizable computation, but memory requirement grows rapidly in line with sequence length. In this paper, we propose a model, called "bi-directional block self-attention network (Bi-BloSAN)", for RNN/CNN-free sequence encoding. It requires as little memory as RNN but with all the merits of SAN. Bi-BloSAN splits the entire sequence into blocks, and applies an intra-block SAN to each block for modeling local context, then applies an inter-block SAN to the outputs for all blocks to capture long-range dependency. Thus, each SAN only needs to process a short sequence, and only a small amount of memory is required. Additionally, we use feature-level attention to handle the variation of contexts around the same word, and use forward/backward masks to encode temporal order information. On nine benchmark datasets for different NLP tasks, Bi-BloSAN achieves or improves upon state-of-the-art accuracy, and shows better efficiency-memory trade-off than existing RNN/CNN/SAN.
BibTeX
@inproceedings{shen2018bi,
  author = {Tao Shen and Tianyi Zhou and Guodong Long and Jing Jiang and Chengqi Zhang},
  title = {{Bi-Directional Block Self-Attention for Fast and Memory-Efficient Sequence Modeling}},
  booktitle = {International Conference on Learning Representations},
  year = {2018},
  url = {https://openreview.net/forum?id=H1cWzoxA-},
}
Figure