Source-linked AI summary
Star-Transformer
Qipeng Guo, Xipeng Qiu, Pengfei Liu, Yunfan Shao, Xiangyang Xue, Zheng Zhang
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.
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.
Results
Across one toy dataset and 21 real datasets, Star-Transformer outperforms standard Transformer and achieves comparable results with state-of-the-art models.
Takeaways & Limitations
Star-Transformer provides a lightweight structure with approximate long-range dependency modeling and reduces connections from n2 to 2n.
Takeaways & Limitations
The study excludes unsupervised and semi-supervised models from comparison and leaves unsupervised pretraining for future work.
Abstract
from arXiv · showhide
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.
- 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.
- The design reduces computation cost from quadratic to linear in sequence length and reduces the number of connections from n2 to 2n.
- Star-Transformer consistently outperforms standard Transformer on Text Classification, Natural Language Inference, and Sequence Labelling, with lower computation complexity.
- Both Transformer and Star-Transformer handle long-range dependencies better than LSTM and BiLSTM on the Masked Summation simulation task.
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.
- 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.
- 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.
- Graph Neural Networks: Unlike previous augmented models, Star-Transformer uses attention alone and is designed for simpler, parallel computation.
- Graph Neural Networks: Its better parallel capacity and lower complexity make Star-Transformer faster than RNNs or Transformer, especially for modeling long sequences.
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.
- Architecture: Radial connections link satellites to the shared relay, making non-adjacent satellites two-hop neighbors for non-local information exchange.
- Architecture: Ring connections join adjacent satellites, including the first and last nodes, to encode local compositionality similarly to CNNs or bidirectional RNNs.
- Architecture: Radial connections capture non-local compositions while ring connections attend to local compositions, allowing both types to be modeled simultaneously.
- Implementation: The implementation uses scaled dot-product multi-head attention, learnable position embeddings, and alternating satellite and relay updates.
- Outputs: After T update rounds, final satellite states support sequence labeling, while max-pooled satellite states mixed with the relay state support classification.
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).
- Long-range dependencies: The relay node can simulate a standard-Transformer relationship hi → hj through hi → s → hj, yielding a constant-two dependency path.
- Efficiency and results: 10 times acceleration on the simulation task and 4.5 times on real tasks are reported for the Star-Transformer.
- Efficiency and results: The model preserves long-input handling and achieves significant improvements on some modestly sized datasets.
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.
- 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.
- Masked Summation: 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.
- 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.
- 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.
- 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.
- 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.
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.
- Star-Transformer outperforms the standard Transformer and achieves comparable results with state-of-the-art models across one toy and 21 real datasets.
- The evaluation excludes unsupervised pre-training, while future work will investigate Star-Transformer with pre-training on a large corpus.