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

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

TL;DR

This paper introduces Bi-BloSAN (Bi-directional Block Self-Attention Network), a novel sequence encoding framework that eliminates the need for RNNs and CNNs in natural language processing. By splitting sequences into local blocks and applying a two-level hierarchical self-attention mechanism, it achieves the high accuracy and parallelizability of standard Self-Attention Networks (SANs) while slashing memory consumption down to RNN-like levels.

What Problem Does This Paper Address?

To understand text, deep learning models use context fusion modules to generate context-aware representations of words. Traditionally, researchers have relied on Recurrent Neural Networks (RNNs) or Convolutional Neural Networks (CNNs). However, RNNs are inherently sequential and slow to train, while CNNs struggle to connect words that are far apart in a sentence.

Self-Attention Networks (SANs), like the Transformer, solved these issues by directly modeling dependencies between all word pairs in parallel. Unfortunately, standard SANs suffer from a massive flaw: their memory requirement grows quadratically ($O(n^2)$) with the sequence length ($n$). Storing the attention scores for every single pair of words quickly exhausts GPU memory on long texts. The authors design Bi-BloSAN to fix this bottleneck, delivering a fast, highly parallelizable attention model that operates within a strict, low memory budget.

Methods

The core innovation of the paper is the Masked Block Self-Attention (mBloSA) module, which splits sequence processing into a two-level hierarchy:

  1. Intra-block Self-Attention: The input sequence is divided into equal, smaller blocks of length $r$. A masked self-attention network is applied to each block independently to capture local context. Because the blocks are short, this step uses very little memory.
  2. Inter-block Self-Attention: A compression mechanism (source2token attention) reduces each block into a single vector. A second masked self-attention network then runs across these block vectors to capture long-range, global context.
  3. Context Fusion Gate: A gating mechanism dynamically merges the original word embeddings, the local block features, and the global context features to produce the final token representations.
Figure 3: Masked block self-attention (mBloSA) mechanism.

To capture temporal order without using recurrent loops, the full Bi-BloSAN architecture runs two mBloSA modules in parallel—one utilizing a forward mask and the other a backward mask. The outputs are concatenated and compressed into a final sequence encoding. Furthermore, the authors mathematically derive an optimal block length ($r = \sqrt[3]{2n}$) to minimize the model's overall memory footprint.

Datasets

The authors evaluated Bi-BloSAN across nine benchmark datasets spanning four distinct NLP tasks:

  • Natural Language Inference (NLI): SNLI dataset.
  • Reading Comprehension: A modified version of the SQuAD dataset, adapted into a sentence-selection task to evaluate sequence encoding power.
  • Semantic Relatedness: SICK dataset.
  • Sentence Classification: Six distinct benchmarks, including Customer Reviews (CR), MPQA (opinion polarity), SUBJ (subjectivity), TREC (question type), and the Stanford Sentiment Treebank (SST-1 and SST-2).

Key Insights and Ideas

  • Divide and Conquer for Attention: Breaking a massive $O(n^2)$ attention matrix into smaller local matrices and a downsampled global matrix effectively linearizes memory growth for typical sequence lengths.
  • Recurrence-Free Bi-directionality: You don't need sequential processing (like LSTMs) to understand word order. Applying forward and backward masks to the attention matrix achieves the same structural awareness while remaining fully parallelizable.
  • Feature-Level Attention: Instead of computing a single scalar attention score per word pair, the model calculates attention at the feature level (multi-dimensional attention), allowing it to better capture words whose meanings shift depending on context.

Key Results

  • The Efficiency-Memory Sweet Spot: As illustrated in Figure 1, Bi-BloSAN achieves state-of-the-art accuracy on the SNLI dataset (85.7%), matching the performance of standard directional self-attention (DiSAN) while using roughly half the GPU memory and training 3-4x faster than standard LSTMs and GRUs.
Figure 1: A comparison of Bi-BloSAN and other RNN/CNN/SAN in terms of train- ing time, training memory consumption and test accuracy on SNLI (Bowman et al., 2015). The details of all the models are pro- vided in Section 4.
  • Reading Comprehension Speedup: On the modified SQuAD task, Bi-BloSAN achieved a development accuracy of 68.38%, outperforming Bi-LSTM (68.01%) and multi-head attention (64.82%) while dramatically reducing training time per epoch compared to the RNN baselines.
  • Robust Classification: Bi-BloSAN achieved top-tier results across all six sentence classification benchmarks (e.g., 94.8% on TREC, 90.4% on MPQA), proving its versatility across different text styles.

Limitations and Future Work

  • Memory vs. Multiplicative Attention: While Bi-BloSAN drastically reduces memory compared to standard additive SANs, it still requires slightly more memory than pure multiplicative attention models (like standard Multi-head attention), which trade away some expressiveness for raw memory savings.
  • Hyperparameter Tuning: The block structure introduces a new hyperparameter (block length $r$). Even though the authors provide a theoretical optimization formula, real-world sequence length variance within mini-batches means empirical tuning is still required.
  • Scope of Tasks: The evaluation focuses entirely on discriminative sequence encoding tasks. The authors do not explore how this block-attention mechanism would perform in generative autoregressive tasks, such as machine translation decoding.

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