Star-Transformer

Qipeng Guo; Xipeng Qiu; Pengfei Liu; Yunfan Shao; Xiangyang Xue; Zheng Zhang

Source-linked AI summary

Star-Transformer

Qipeng Guo, Xipeng Qiu, Pengfei Liu, Yunfan Shao, Xiangyang Xue, Zheng Zhang

arXiv:1902.09113v3Feb 25, 2019cs.CL

TL;DR

Transformer’s fully connected attention has quadratic complexity and often depends on large training corpora, especially for modestly sized datasets. Star-Transformer sparsifies this topology into a star-shaped structure with ring and radial connections, reducing computation while retaining local and long-range modeling. Across one toy and 21 real datasets, it outperforms standard Transformer and achieves comparable results with state-of-the-art models.

Problem
Transformer has quadratic computation overhead and commonly requires large training corpora when applied to modestly sized datasets.
Source: §1 · p. 1
Method
Star-Transformer sparsifies fully connected attention into a star-shaped topology with ring connections for local composition and radial connections for non-local communication.
Source: §1 · p. 2
Results
Across one toy dataset and 21 real datasets, Star-Transformer outperforms standard Transformer and achieves comparable results with state-of-the-art models.
Source: §6 · p. 8
Takeaways & Limitations
Star-Transformer provides a lightweight structure with approximate long-range dependency modeling and reduces connections from n2 to 2n.
Source: §1 · p. 2
The study excludes unsupervised and semi-supervised models from comparison and leaves unsupervised pretraining for future work.
Source: §5 · p. 5, §6 · p. 8

Abstract

from arXiv · show

Although Transformer has achieved great successes on many NLP tasks, its heavy structure with fully-connected attention connections leads to dependencies on large training data. In this paper, we present Star-Transformer, a lightweight alternative by careful sparsification. To reduce model complexity, we replace the fully-connected structure with a star-shaped topology, in which every two non-adjacent nodes are connected through a shared relay node. Thus, complexity is reduced from quadratic to linear, while preserving capacity to capture both local composition and long-range dependency. The experiments on four tasks (22 datasets) show that Star-Transformer achieved significant improvements against the standard Transformer for the modestly sized datasets.

1 Introduction

The paper introduces Star-Transformer to address Transformer’s quadratic complexity and sensitivity to limited training data by sparsifying its topology while retaining local and long-range modeling. Experiments report consistent improvements over standard Transformer across NLP tasks, with a simulation analysis supporting long-range dependency handling.

Transformer’s quadratic overhead becomes especially problematic for long sentences, and limited-data settings often require large-corpus pretraining.Source: §1 · p. 1
Star-Transformer replaces fully connected attention with a star-shaped structure using radial connections for non-local communication and ring connections for local composition.The ring connections encode a local-compositionality prior, while radial connections preserve non-local communication.Source: §1 · pp. 1–2
The design reduces computation cost from quadratic to linear in sequence length and reduces the number of connections from n2 to 2n.Source: §1 · p. 2
Star-Transformer consistently outperforms standard Transformer on Text Classification, Natural Language Inference, and Sequence Labelling, with lower computation complexity.Source: §1 · p. 2
Both Transformer and Star-Transformer handle long-range dependencies better than LSTM and BiLSTM on the Masked Summation simulation task.Source: §1 · p. 2

2 Related Work

Related work contrasts local-composition models such as CNNs and RNNs with self-attention methods that capture non-local dependencies but often need large training corpora. Star-Transformer combines local and non-local modeling through a parallelizable star-shaped graph using attention alone.

Modelling Local Compositionality

CNNs and RNNs encode local composition but are described as difficult for capturing long-term dependencies in text sequences.Source: §2 · p. 2

Modelling Non-Local Compositionality

Self-attention methods aggregate information for non-local composition, while Transformer-based models commonly require large training corpora on modestly sized datasets.Source: §2 · pp. 2–3

Graph Neural Networks

Star-Transformer introduces a virtual relay node in a star-shaped graph, balancing local and non-local compositionality through ring and radial connections.Source: §2 · p. 3
Unlike previous augmented models, Star-Transformer uses attention alone and is designed for simpler, parallel computation.Source: §2 · p. 3
Its better parallel capacity and lower complexity make Star-Transformer faster than RNNs or Transformer, especially for modeling long sequences.Source: §2 · p. 3

3 Model

Star-Transformer uses a relay node, satellite nodes, and radial and ring connections to combine non-local communication with local sequence composition. Its attention-based updates alternate between satellite and relay states before task-specific outputs are produced.

Architecture

The model contains one relay node and n satellite nodes, with each satellite representing one token and the relay gathering and scattering information.Source: §3.1 · p. 3
Radial connections link satellites to the shared relay, making non-adjacent satellites two-hop neighbors for non-local information exchange.Source: §3.1 · p. 3
Ring connections join adjacent satellites, including the first and last nodes, to encode local compositionality similarly to CNNs or bidirectional RNNs.Source: §3.1 · p. 3
Radial connections capture non-local compositions while ring connections attend to local compositions, allowing both types to be modeled simultaneously.Source: §3.1 · p. 3

Implementation

The implementation uses scaled dot-product multi-head attention, learnable position embeddings, and alternating satellite and relay updates.Source: §3.2 · pp. 3–4

Outputs

After T update rounds, final satellite states support sequence labeling, while max-pooled satellite states mixed with the relay state support classification.Source: §3.3 · p. 4

4 Comparison to the standard Transformer

Compared with the standard Transformer, Star-Transformer replaces pairwise connections with gather-and-dispatch through a sparse topology. This reduces computation while retaining long-range dependency handling and improving results on modestly sized datasets.

Complexity

O(6nd) replaces O(n^2d) per-layer computation for Star-Transformer and the standard Transformer, respectively.The ring update costs O(5nd), while radial updates cost O(nd).Source: §4 · p. 4

Long-range dependencies

The relay node can simulate a standard-Transformer relationship hi → hj through hi → s → hj, yielding a constant-two dependency path.Source: §4 · p. 4

Efficiency and results

10 times acceleration on the simulation task and 4.5 times on real tasks are reported for the Star-Transformer.Source: §4 · p. 5
The model preserves long-input handling and achieves significant improvements on some modestly sized datasets.Source: §4 · p. 5

5 Experiments

Experiments evaluate Star-Transformer on a synthetic long-range-dependency task and three NLP task groups, showing efficient performance and strong results on modestly sized datasets.

Experimental Setup

The evaluation covers one simulation task and three real tasks: text classification, natural language inference, and sequence labeling.The real-task benchmarks include SST, MTL-16, SNLI, POS tagging, and NER datasets.Source: §5 · p. 5, §5.2 · p. 6, §5.3 · p. 7

Masked Summation

The masked summation task tests whether models can identify masked vectors and sum them across distant positions.Its input is a matrix with n columns, mask values in the first dimension, and an implicit k controlling the number of selected columns.Source: §5.1 · p. 5, Figure 2 · p. 6
Star-Transformer preserves long-range dependency performance as sequence length increases, whereas LSTM and BiLSTM performance drops quickly.Both Transformer variants perform consistently across the tested lengths.Source: §5.1 · pp. 5–6

Text Classification

On SST, Star-Transformer improves by 2.5 points over standard Transformer, while on MTL-16 it improves average accuracy by 4.2 and wins all 16 datasets.The MTL-16 benchmark contains 16 small datasets across various domains.Source: §5.2 · p. 6

Natural Language Inference

On SNLI, Star-Transformer beats standard Transformer by a large margin and outperforms most typical baselines with results comparable to the state of the art.The comparison uses sentence-vector representations for premise and hypothesis sentences.Source: §5.3 · p. 7

Sequence Labelling

On sequence labeling, Star-Transformer achieves state-of-the-art performance and significantly outperforms standard Transformer, including without a CRF layer.The evaluated tasks are POS tagging and NER; character-enhanced Star-Transformer beats most competitors.Source: §5.4 · pp. 7–8, Table 5 · p. 8

Ablation Study

Ablations show that both radial and ring connections are necessary: removing radial connections harms long-range handling, while removing ring connections heavily damages real-task performance.The radial-only variant remains functional on the simulation task but loses local-task performance; the ring-only variant loses long-range capability.Source: §5.5 · p. 8

6 Conclusion and Future Works

Star-Transformer reduces Transformer’s computation complexity while outperforming the standard Transformer across broad evaluations. The work excludes unsupervised pre-training and identifies its future investigation as an open direction.

Star-Transformer reduces the standard Transformer’s computation complexity through careful topology sparsification.Source: §6 · p. 8
Star-Transformer outperforms the standard Transformer and achieves comparable results with state-of-the-art models across one toy and 21 real datasets.Source: §6 · p. 8
The evaluation excludes unsupervised pre-training, while future work will investigate Star-Transformer with pre-training on a large corpus.Source: §6 · p. 8