Efficient Long Sequence Encoding via Synchronization

Xiangyang Mou, Mo Yu, Bingsheng Yao, Lifu HuangarXiv 2022 · DOI · arXiv

Abstract

Standard Transformer models struggle with long-range dependencies due to the quadratic complexity of self-attention. This paper introduces TRANSYNC, a framework that enables efficient processing of long sequences by synchronizing information across segments via "anchor tokens." TRANSYNC achieves state-of-the-art results on complex reasoning benchmarks like NarrativeQA and HotpotQA while maintaining high computational efficiency and reduced memory overhead.

The Long-Range Problem in Transformers

Self-attention mechanisms in standard Transformers (e.g., BERT, GPT) scale quadratically ($O(l^2)$) with input length. This makes processing extensive documents or multi-document sets computationally prohibitive on standard hardware. Existing solutions typically follow two paths: sparse attention, which may miss distant connections, or hierarchical encoding, which often results in "shallow" information exchange where global context is only integrated at the final stages of processing.

The TRANSYNC Framework

TRANSYNC (Transformer with Synchronization) addresses these limitations by establishing "bridges" between segments using anchors. The process involves four key steps:

  1. Segmentation: Long inputs are divided into manageable chunks, each prefixed with the user's question to maintain local relevance.
  2. Anchor Identification: Specific tokens (e.g., document titles, special separators, or task-relevant entities) are identified as anchors across segments.
  3. Synchronization Module: Within every Transformer layer, a synchronization step occurs after local attention. Anchor tokens belonging to the same group (e.g., occurrences of the same title across different chunks) exchange information via a dedicated self-attention module.
  4. Iterative Propagation: By synchronizing at every layer, the model facilitates deep information flow, allowing a complex, global understanding to emerge incrementally as the text is processed.
Figure 1: Visualization of multi-hop reasoning where anchors like "House of Anubis" and "Het Huis Anubis" link information across disparate document segments to answer a query.

Experimental Evaluation

The framework was evaluated on two challenging benchmarks designed to test long-range reasoning:

  • NarrativeQA (Summary Setting): Requires answering questions based on long book and movie script summaries, testing single-document comprehension.
  • HotpotQA (Wild Multi-hop Reasoning): A modified version where the model must find a chain of evidence across two relevant documents hidden among eight "distractor" documents.

Key Results and Efficiency

TRANSYNC consistently outperformed established baselines, including the strong Fusion-in-Decoder (FiD) and ETC methods.

Figure 2: Performance comparison showing TRANSYNC achieving state-of-the-art results across NarrativeQA and MultiHop-QA benchmarks.

As shown in the performance table, TRANSYNC achieves a consistent improvement (approximately 1% in Rouge-L and F1 scores) over competitive models. Beyond accuracy, the model demonstrates significant efficiency gains. On the NarrativeQA dataset, TRANSYNC was roughly 2x faster than the standard BART baseline, processing tokens in 134 $\mu$s compared to 292 $\mu$s. This efficiency stems from its ability to maintain a lower computational complexity ($O((l_q + \frac{l_c}{n})^2 \cdot n)$) compared to the standard quadratic approach.

Discussion and Future Work

The success of TRANSYNC highlights the importance of deep, layer-wise synchronization for long-context tasks. By using anchors as bridges, the model mimics human reading behavior—linking new information back to previously established entities.

While the current implementation relies on heuristic anchor selection (such as titles), future work could explore automated anchor discovery, where the model learns to identify the most critical "bridge" tokens dynamically. Additionally, scaling this synchronization mechanism to massive models with tens of billions of parameters remains an open and promising research direction.

Summary updated

Abstract

Pre-trained Transformer models have achieved successes in a wide range of NLP tasks, but are inefficient when dealing with long input sequences. Existing studies try to overcome this challenge via segmenting the long sequence followed by hierarchical encoding or post-hoc aggregation. We propose a synchronization mechanism for hierarchical encoding. Our approach first identifies anchor tokens across segments and groups them by their roles in the original input sequence. Then inside Transformer layer, anchor embeddings are synchronized within their group via a self-attention module. Our approach is a general framework with sufficient flexibility -- when adapted to a new task, it is easy to be enhanced with the task-specific anchor definitions. Experiments on two representative tasks with different types of long input texts, NarrativeQA summary setting and wild multi-hop reasoning from HotpotQA, demonstrate that our approach is able to improve the global information exchange among segments while maintaining efficiency.
BibTeX
@misc{mou2022efficient,
  author = {Xiangyang Mou and Mo Yu and Bingsheng Yao and Lifu Huang},
  title = {{Efficient Long Sequence Encoding via Synchronization}},
  year = {2022},
  eprint = {2203.07644},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2203.07644},
}
Figure