Back

Your Transformer May Not be as Powerful as You Expect

Shengjie LuoShanda LiShuxin ZhengTie-Yan LiuLiwei WangDi He

article2022NeurIPS65 citations

Proves that standard relative positional encoding prevents Transformers from being universal function approximators due to softmax stochasticity, and introduces a mathematically grounded alternative attention module that restores full expressive capacity with minimal parameter overhead.

Listen

Modern artificial intelligence architectures, particularly Transformer models, increasingly rely on Relative Positional Encoding (RPE) to track distances between elements in sequences, images, and graph structures. While empirical studies show that RPE enhances generalization over long sequences compared to traditional Absolute Positional Encoding (APE), the theoretical capabilities of RPE-based models have remained largely unexamined. This article investigates whether RPE-equipped Transformers possess the theoretical capacity to approximate any continuous sequence-to-sequence mapping, a property known as universal function approximation.

The main objective of the article is to mathematically analyze the expressive power of RPE-based Transformers and develop an enhanced architecture that guarantees universal function approximation. To evaluate these properties, the authors conduct rigorous mathematical proofs alongside empirical validations across synthetic tasks, large-scale language modeling on the WikiText-103 dataset, and molecular graph property prediction on the ZINC and PCQM4M benchmark datasets.

The investigation yields several critical findings. First, the article proves that standard RPE-based Transformers are not universal function approximators, regardless of their depth or width, because standard RPE operations force the attention mechanism to output a right stochastic matrix that suppresses positional signals. Second, the authors formulate two theoretical conditions—an attentive condition and a position-aware condition—that restore universal expressiveness. Third, building on these conditions, they introduce Universal RPE-based (URPE) Attention, which applies a lightweight learnable Toeplitz matrix multiplication to the attention map. In practical experiments, URPE achieved 100% accuracy on synthetic position-dependent tasks where standard RPE achieved under 60%. Furthermore, URPE reduced validation perplexity from 23.1 to 22.4 on WikiText-103 and decreased test error by more than 40% on ZINC molecular property benchmarks, all while adding minimal parameters (approximately 4,000 in a 151-million-parameter model) and negligible computational overhead.

These findings indicate that existing RPE models carry architectural bottlenecks that restrict model capacity, especially for position-sensitive tasks. The URPE framework resolves this fundamental deficiency with essentially zero risk to computational budgets, inference latency, or memory consumption. Organizations deploying Transformer backbones can adopt URPE by initializing the new parameters as all-one matrices, enabling seamless fine-tuning of existing pre-trained models without training from scratch.

Decision-makers and engineering teams should consider integrating URPE into current Transformer pipelines, particularly for applications in natural language generation, molecular modeling, and graph learning. However, stakeholders should note that the primary mathematical proofs assume simplified architectures without normalization layers and evaluate bounded input domains. Further testing across additional diverse domain benchmarks is recommended to fully establish performance across other complex tasks.

Carnegie Mellon UniversityMicrosoftPeking UniversityZhejiang Labencoder-decoderfunction approximatorsstochasticRPE-based Transformerexpressive poweruniversal function approximation
arXiv: 2205.13401lsj2408/URPE
Cover for Your Transformer May Not be as Powerful as You Expect

Abstract

Relative Positional Encoding (RPE), which encodes the relative distance between any pair of tokens, is one of the most successful modifications to the original Transformer. As far as we know, theoretical understanding of the RPE-based Transformers is largely unexplored. In this work, we mathematically analyze the power of RPE-based Transformers regarding whether the model is capable of approximating any continuous sequence-to-sequence functions. One may naturally assume the answer is in the affirmative—RPE-based Transformers are universal function approximators. However, we present a negative result by showing there exist continuous sequence-to-sequence functions that RPE-based Transformers cannot approximate no matter how deep and wide the neural network is. One key reason lies in that most RPEs are placed in the softmax attention that always generates a right stochastic matrix. This restricts the network from capturing positional information in the RPEs and limits its capacity. To overcome the problem and make the model more powerful, we first present sufficient conditions for RPE-based Transformers to achieve universal function approximation. With the theoretical guidance, we develop a novel attention module, called Universal RPE-based (URPE) Attention, which satisfies the conditions. Therefore, the corresponding URPE-based Transformers become universal function approximators. Extensive experiments covering typical architectures and tasks demonstrate that our model is parameter-efficient and can achieve superior performance to strong baselines in a wide range of applications. The code will be made publicly available at https://github.com/lsj2408/URPE.

Topics

encoder-decoderfunction approximatorsstochasticsufficient conditionsfeedforward neural networks

Keywords

RPE-based Transformerexpressive poweruniversal function approximationGraph TransformersGraphormer modelsoftmax attentionpositional encodingTransformer architecture

Table of Contents

  • 1 Introduction
  • 2 Preliminary
  • 3 Transformers with RPE are not Universal Approximators
  • 4 Making RPE-based Transformers Universal Approximators
  • 4.1 A Sufficient Condition to Achieve Universal Approximation
  • 4.2 A Universal RPE-based Transformer
  • 5 Experiments
  • 5.1 Synthetic Tasks
  • 5.2 Language Modeling
  • 5.3 Graph Learning
  • 5.4 More Analyses
  • 6 Related Work
  • 7 Conclusion
  • Acknowledgements
  • References
  • Checklist

Knowls

  1. Knowl 1 — Non-Universality of Standard RPE-Based Transformers

    theoretical result

    For sequence length n>2n > 2, token embedding dimension d≥1d \ge 1, and domain D⊆Rn×d\mathcal{D} \subseteq \mathbb{R}^{n \times d} containing the all-zero matrix 0\mathbf{0}, standard Relative Positional Encoding (RPE) Transformers are not universal approximators of continuous sequence-to-sequence functions.

    Let ΩRPEH,dH,r\Omega_{\text{RPE}}^{H, d_H, r} denote the function class of Transformers composed of stacked Transformer blocks where the attention matrix for head hh is parameterized as: ARPEh(X)=softmax(XWQh(XWKh)⊤+B)A^h_{\text{RPE}}(X) = \text{softmax}\left(X W_Q^h (X W_K^h)^\top + B\right) where X∈Rn×dX \in \mathbb{R}^{n \times d}, WQh,WKh∈Rd×dHW_Q^h, W_K^h \in \mathbb{R}^{d \times d_H}, and B∈Rn×nB \in \mathbb{R}^{n \times n} is any relative positional encoding matrix mapping from XX to Rn×n\mathbb{R}^{n \times n} (such as Shaw's RPE, T5 Toeplitz bias, Transformer-XL bias, or DeBERTa bias).

    For any M>0M > 0, there exists a continuous function g~M:D→Rn×d\tilde{g}_M: \mathcal{D} \to \mathbb{R}^{n \times d} such that: sup⁡X∈D∥g~M(X)−g(X)∥F>M\sup_{X \in \mathcal{D}} \|\tilde{g}_M(X) - g(X)\|_F > M holds for every g∈ΩRPEH,dH,rg \in \Omega_{\text{RPE}}^{H, d_H, r}, regardless of the number of attention heads HH, head dimension dHd_H, feed-forward dimension rr, or network depth L∈N∗L \in \mathbb{N}^*.

    The failure of universal approximation stems from the fact that ARPEh(X)A^h_{\text{RPE}}(X) is normalized via softmax to always produce a right stochastic matrix (ARPEh(X)1n=1nA^h_{\text{RPE}}(X)\mathbf{1}_n = \mathbf{1}_n). When the input sequence consists of nn identical tokens (e.g., all zeros), every subsequent layer output and normalization operation preserves row-identical matrices, making it impossible to approximate position-dependent sequence functions such as g~M(X)=(2M,0,…,0)⊤\tilde{g}_M(X) = (2M, 0, \dots, 0)^\top.

  2. Knowl 2 — Sufficient Conditions for Universal Approximation of Sequence-to-Sequence Functions

    theoretical result

    Let n,d∈N∗n, d \in \mathbb{N}^*, p∈[1,∞)p \in [1, \infty), ε>0\varepsilon > 0, D⊂Rn×d\mathcal{D} \subset \mathbb{R}^{n \times d} be a compact domain, and f:D→Rn×df: \mathcal{D} \to \mathbb{R}^{n \times d} be any continuous sequence-to-sequence function. Consider a generalized self-attention layer without normalization layers: AttnU(X)=X+∑h=1HAUh(X)XWVhWOh\text{Attn}_U(X) = X + \sum_{h=1}^H A_U^h(X) X W_V^h W_O^h and the corresponding Transformer function class ΩUH,dH,r\Omega_U^{H, d_H, r} formed by compositions of such blocks with feed-forward layers FFN(X)=X+ReLU(XW1)W2\text{FFN}(X) = X + \text{ReLU}(X W_1) W_2, where WOh∈RdH×dW_O^h \in \mathbb{R}^{d_H \times d}, WQh,WKh,WVh∈Rd×dHW_Q^h, W_K^h, W_V^h \in \mathbb{R}^{d \times d_H}, W1∈Rd×rW_1 \in \mathbb{R}^{d \times r}, and W2∈Rr×dW_2 \in \mathbb{R}^{r \times d}.

    The function class ΩU2,1,4\Omega_U^{2, 1, 4} can approximate ff within an ε\varepsilon error in entry-wise LpL^p norm: (∫D∥f(X)−g(X)∥pp dX)1/p<ε\left( \int_{\mathcal{D}} \|f(X) - g(X)\|_p^p \, dX \right)^{1/p} < \varepsilon for some g∈ΩU2,1,4g \in \Omega_U^{2, 1, 4}, provided that the attention matrix mapping AUh:Rn×d→Rn×nA_U^h: \mathbb{R}^{n \times d} \to \mathbb{R}^{n \times n} satisfies two conditions:

    1. Attentive condition: For any u∈Rd×1u \in \mathbb{R}^{d \times 1} and c∈Rc \in \mathbb{R}, there exists a parametrization of AUhA_U^h such that: AUh(X)=softmax(Xu(Xu−c1n)⊤)A_U^h(X) = \text{softmax}\left(Xu(Xu - c\mathbf{1}_n)^\top\right)

    2. Position-aware condition: There exists a parametrization of AUhA_U^h and a vector v∈Rnv \in \mathbb{R}^n with all distinct entries (vi≠vjv_i \ne v_j for all i≠ji \ne j) such that: AUh(X)1n=vfor all X∈Rn×dA_U^h(X)\mathbf{1}_n = v \quad \text{for all } X \in \mathbb{R}^{n \times d}

    Breaking the right-stochastic constraint (AUh(X)1n=1nA_U^h(X)\mathbf{1}_n = \mathbf{1}_n) via the position-aware condition ensures that positional information is preserved even when input tokens are identical.

  3. Knowl 3 — Universal Relative Positional Encoding Attention

    model/method

    Universal RPE-based (URPE) Attention modifies self-attention by applying an element-wise (Hadamard) product with a learnable Toeplitz matrix to the post-softmax attention matrix: AU(X)=softmax(XWQ(XWK)⊤+B)⊙CA_U(X) = \text{softmax}\left(X W_Q (X W_K)^\top + B\right) \odot C where:

    • X∈Rn×dX \in \mathbb{R}^{n \times d} is the input sequence of length nn and embedding dimension dd.
    • WQ,WK∈Rd×dHW_Q, W_K \in \mathbb{R}^{d \times d_H} are query and key projection matrices.
    • B∈Rn×nB \in \mathbb{R}^{n \times n} is an arbitrary relative positional encoding matrix.
    • ⊙\odot denotes entry-wise matrix multiplication.
    • C∈Rn×nC \in \mathbb{R}^{n \times n} is a learnable Toeplitz matrix, where every element along each descending diagonal from left to right is constant (Ci,j=ci−jC_{i,j} = c_{i-j}).

    Because an n×nn \times n Toeplitz matrix has 2n−12n - 1 degrees of freedom, matrix CC adds only 2n−12n - 1 learnable parameters per attention head. To maximize parameter efficiency, CC is shared across Transformer layers while remaining unique per attention head.

    Practical adaptations:

    • Initialization: CC is initialized as an all-ones matrix (C=1n×nC = \mathbf{1}_{n \times n}), making URPE identical to the standard RPE baseline at initialization and enabling existing pre-trained RPE models to be fine-tuned directly.
    • Causal Masking: For autoregressive tasks, causal constraints are maintained by setting Ci,j=0C_{i,j} = 0 for all i>ji > j.

  4. Knowl 4 — Universal Approximation Guarantee for URPE Transformers

    theoretical result

    URPE-based Attention defined by: AU(X)=softmax(XWQ(XWK)⊤+B)⊙CA_U(X) = \text{softmax}\left(X W_Q (X W_K)^\top + B\right) \odot C with a learnable Toeplitz matrix C∈Rn×nC \in \mathbb{R}^{n \times n} satisfies both the attentive condition and the position-aware condition.

    Consequently, for any sequence length n∈N∗n \in \mathbb{N}^* and embedding dimension d∈N∗d \in \mathbb{N}^*, Transformer networks utilizing URPE-based Attention with 2 heads, head dimension dH=1d_H = 1, and feed-forward hidden dimension r=4r = 4 (the function class ΩU2,1,4\Omega_U^{2, 1, 4}) are universal approximators for continuous sequence-to-sequence functions mapping a compact domain in Rn×d\mathbb{R}^{n \times d} to Rn×d\mathbb{R}^{n \times d}.

  5. Knowl 5 — Synthetic Task Verification of RPE Expressiveness Limitation

    empirical result

    To empirically verify the expressive limitation of standard RPE and the universal capability of URPE, models were evaluated on two sequence-to-sequence synthetic tasks with sequence length n=128n=128, hidden dimension 768768, 3 layers, and 12 attention heads across vocabulary sizes ∣V∣∈{10,1000,10000}|V| \in \{10, 1000, 10000\}:

    1. Position Identification (PI): Given sequence s=(w1,w2,…,wn)s = (w_1, w_2, \dots, w_n), the task predicts the position index sequence: fPI(w1,w2,…,wn)=(1,2,…,n)f_{\text{PI}}(w_1, w_2, \dots, w_n) = (1, 2, \dots, n)

    2. Even Token Prediction (ETP): Given sequence s=(w1,w2,…,wn)s = (w_1, w_2, \dots, w_n), the task outputs even-positioned input tokens in the first half and End-Of-Sentence (EOS) tokens in the second half: fETP(w1,w2,…,wn)=(w2,w4,…,wn,EOS,…,EOS)f_{\text{ETP}}(w_1, w_2, \dots, w_n) = (w_2, w_4, \dots, w_n, \text{EOS}, \dots, \text{EOS})

    Results:

    • Transformers without positional encoding (noPE) and Transformers with T5-style RPE failed on both tasks, achieving less than 60%60\% token-level accuracy across all vocabulary sizes (and near 0%0\% accuracy on the PI task).
    • The URPE-based Transformer consistently achieved 100%100\% token-level accuracy on both PI and ETP tasks across all vocabulary sizes.

    Learned parameter visualizations demonstrate that matrix BB and matrix CC learn complementary representations: BB modulates query-key attention logits inside the softmax, while CC alters row sums outside the softmax to communicate absolute and relative positional information.

  6. Knowl 6 — Language Modeling Benchmark on WikiText-103

    data/table

    Language modeling performance of Transformer-XL with and without URPE-based Attention evaluated on the WikiText-103 dataset (103M tokens, 28K articles, average length 3.6K tokens per article). The backbone Transformer-XL model consists of 16 layers, 10 attention heads, hidden dimension 410, and feed-forward dimension 2100 (151M parameters). Adding URPE introduces approximately 4K additional parameters.

    Model #Params Valid Perplexity Test Perplexity
    LSTM - / 48.7
    TCN - / 45.2
    GCNN-8 - / 44.9
    LSTM+Neural cache - / 40.8
    GCNN-14 - / 37.2
    QRNN 151M / 33.0
    Hebbian+Cache - / 29.9
    Transformer-XL Base 151M 23.1 24.0
    Transformer-XL Base + URPE-based Attention (ours) 151M 22.4 23.2

    Equipping Transformer-XL with URPE-based Attention reduces validation perplexity from 23.1 to 22.4 and test perplexity from 24.0 to 23.2, achieving a 0.8 test perplexity reduction with negligible parameter overhead (~4K parameters).

  7. Knowl 7 — Molecular Graph Representation Learning on ZINC and PCQM4M

    data/table

    Performance of URPE-based Attention integrated into Graphormer on molecular graph regression benchmarks: ZINC (250K molecular graphs; regression on constrained solubility) and PCQM4M from OGB-LSC (3.8M molecular graphs; quantum chemistry regression on HOMO-LUMO gap).

    On ZINC, models operate under a 500K parameter budget (12 layers, hidden/FFN dimension 80, 32 heads). On PCQM4M, the model uses 6 layers, hidden/FFN dimension 512, and 32 heads (12.5M parameters). Graphormer computes the shortest-path distance between node pairs and encodes it as bias BB inside softmax attention; URPE multiplies this attention matrix entry-wise by learnable matrix CC.

    Model (ZINC) #Params Test MAE (ZINC-Subset) Test MAE (ZINC-Full)
    GIN 509,549 0.526 ±\pm 0.051 0.088 ±\pm 0.002
    GraphSAGE 505,341 0.398 ±\pm 0.002 0.126 ±\pm 0.003
    GAT 531,345 0.384 ±\pm 0.007 0.111 ±\pm 0.002
    GCN 505,079 0.367 ±\pm 0.011 0.113 ±\pm 0.002
    MoNet 504,013 0.292 ±\pm 0.006 0.090 ±\pm 0.002
    GatedGCN-PE 505,011 0.214 ±\pm 0.006 -
    MPNN(sum) 480,805 0.145 ±\pm 0.007 -
    HIMP 614,516 0.151 ±\pm 0.006 0.036 ±\pm 0.002
    PNA 387,155 0.142 ±\pm 0.010 -
    GT 588,929 0.226 ±\pm 0.014 -
    SAN 508,577 0.139 ±\pm 0.006 -
    Graphormer 489,321 0.122 ±\pm 0.006 0.052 ±\pm 0.005
    Graphormer+URPE-based Attention (ours) 491,737 0.086 ±\pm 0.007 0.028 ±\pm 0.002
    Model (PCQM4M) #Params Valid MAE
    GCN 2.0M 0.1691
    GIN 3.8M 0.1537
    GCN-VN 4.9M 0.1485
    GIN-VN 6.7M 0.1395
    GINE-VN 13.2M 0.1430
    DeeperGCN-VN 25.5M 0.1398
    GT 0.6M 0.1400
    GT-Wide 83.2M 0.1408
    Graphormer 12.5M 0.1264
    Graphormer + URPE-based Attention (ours) 12.5M 0.1238

    On ZINC-Subset, URPE reduces test MAE from 0.122 to 0.086 (a 29.5% relative error reduction); on ZINC-Full, test MAE drops from 0.052 to 0.028 (a 46.2% relative error reduction). On PCQM4M, URPE lowers validation MAE from 0.1264 to 0.1238.

  8. Knowl 8 — Effect of Model Depth on URPE Transformer-XL Performance

    data/table

    Validation perplexity comparison across network depths L∈{4,8,16}L \in \{4, 8, 16\} on the WikiText-103 dataset, evaluating standard Transformer-XL against Transformer-XL equipped with URPE-based Attention (10 attention heads, hidden dimension 410, feed-forward dimension 2100).

    Model L=4L = 4 L=8L = 8 L=16L = 16
    Transformer-XL 29.6 26.0 23.1
    Transformer-XL + URPE-based Attention (ours) 28.7 25.2 22.4

    URPE-based Attention consistently lowers perplexity across all model depths (-0.9 at L=4L=4, -0.8 at L=8L=8, and -0.7 at L=16L=16), showing that the expressive benefits of URPE persist across different network sizes.

  9. Knowl 9 — Inference Latency and Memory Usage Profiling of URPE Attention

    data/table

    Inference runtime (milliseconds, reported in log⁡2\log_2 scale) and peak GPU memory usage (GB) evaluated on a 16GB NVIDIA Tesla V100 GPU using a 12-layer vanilla Transformer backbone (hidden dimension 768, 12 attention heads, batch size 32) across sequence lengths N∈{128,256,512}N \in \{128, 256, 512\}.

    Model Inference Runtime (log⁡2\log_2 ms) Peak Memory Usage (GB)
    N=128N = 128 N=256N = 256 N=512N = 512 N=128N = 128 N=256N = 256 N=512N = 512
    RPE-based Transformer 4.55 5.60 6.79 0.96 1.12 1.86
    URPE-based Transformer (ours) 4.59 5.66 6.91 0.97 1.17 2.04

    URPE introduces only minor computational overhead compared to standard RPE across all tested sequence lengths (e.g., runtime increases from 4.55 to 4.59 log⁡2\log_2 ms at N=128N=128, and peak memory usage increases from 1.86 GB to 2.04 GB at N=512N=512).

Coverage note — None omitted; the extraction covers all core contributions of the paper, including the negative expressiveness theorem of standard RPE Transformers, the sufficient conditions for universal sequence-to-sequence approximation, the URPE attention architecture and proposition, synthetic task verifications, language modeling benchmarks, graph learning benchmarks, depth scaling ablations, and computational profiling.

References

  1. 1.Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.06450, 2016.
  2. 2.Shaojie Bai, J Zico Kolter, and Vladlen Koltun. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling. arXiv preprint arXiv:1803.01271, 2018.
  3. 3.Hangbo Bao, Li Dong, Furu Wei, Wenhui Wang, Nan Yang, Xiaodong Liu, Yu Wang, Songhao Piao, Jianfeng Gao, Ming Zhou, et al. Unilmv2: Pseudo-masked language models for unified language model pre-training. arXiv preprint arXiv:2002.12804, 2020.
  4. 4.Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine learning, 14(1):115–133, 1994.
  5. 5.Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint arXiv:1711.07553, 2017.
  6. 6.Rémy Brossard, Oriel Frigo, and David Dehaene. Graph convolutions that can finally model local structure. arXiv preprint arXiv:2011.15069, 2020.
  7. 7.Jean-Baptiste Cordonnier, Andreas Loukas, and Martin Jaggi. On the relationship between self-attention and convolutional layers. In International Conference on Learning Representations, 2020.
  8. 8.Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260–13271, 2020.
  9. 9.George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303–314, 1989.
  10. 10.Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G Carbonell, Quoc Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond a fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2978–2988, 2019.
  11. 11.Yann N Dauphin, Angela Fan, Michael Auli, and David Grangier. Language modeling with gated convolutional networks. In International conference on machine learning, pages 933–941. PMLR, 2017.
  12. 12.Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018.
  13. 13.Yihe Dong, Jean-Baptiste Cordonnier, and Andreas Loukas. Attention is not all you need: Pure attention loses rank doubly exponentially with depth. In International Conference on Machine Learning, pages 2793–2803. PMLR, 2021.
  14. 14.Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
  15. 15.Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
  16. 16.Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982, 2020.
  17. 17.Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning on molecular graphs. arXiv preprint arXiv:2006.12179, 2020.
  18. 18.Gerald B Folland. Real analysis: modern techniques and their applications, volume 40. John Wiley & Sons, 1999.
  19. 19.Ken-Ichi Funahashi. On the approximate realization of continuous mappings by neural networks. Neural networks, 2(3):183–192, 1989.
  20. 20.Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pages 1263–1272. PMLR, 2017.
  21. 21.Edouard Grave, Armand Joulin, and Nicolas Usunier. Improving neural language models with a continuous cache. arXiv preprint arXiv:1612.04426, 2016.
  22. 22.Robert M Gray. Toeplitz and circulant matrices: A review. now publishers inc, 2006.
  23. 23.Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
  24. 24.Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width. arXiv preprint arXiv:1710.11278, 2017.
  25. 25.Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhanced bert with disentangled attention. arXiv preprint arXiv:2006.03654, 2020.
  26. 26.Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhanced bert with disentangled attention. In International Conference on Learning Representations, 2021.
  27. 27.Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2):251–257, 1991.
  28. 28.Jiri Hron, Yasaman Bahri, Jascha Sohl-Dickstein, and Roman Novak. Infinite attention: Nngp and ntk for deep attention networks. In International Conference on Machine Learning, pages 4376–4386. PMLR, 2020.
  29. 29.Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-lsc: A large-scale challenge for machine learning on graphs. arXiv preprint arXiv:2103.09430, 2021.
  30. 30.Gao Huang, Yu Sun, Zhuang Liu, Daniel Sedra, and Kilian Q Weinberger. Deep networks with stochastic depth. In European conference on computer vision, pages 646–661. Springer, 2016.
  31. 31.Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models out-performs graph neural networks. In International Conference on Learning Representations, 2020.
  32. 32.Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448–456. PMLR, 2015.
  33. 33.Guolin Ke, Di He, and Tie-Yan Liu. Rethinking positional encoding in language pre-training. In International Conference on Learning Representations, 2021.
  34. 34.Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
  35. 35.Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016.
  36. 36.Nikita Kitaev and Dan Klein. Constituency parsing with a self-attentive encoder. arXiv preprint arXiv:1805.01052, 2018.
  37. 37.Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34, 2021.
  38. 38.Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergcn: All you need to train deeper gcns. arXiv preprint arXiv:2006.07739, 2020.
  39. 39.Yang Li, Si Si, Gang Li, Cho-Jui Hsieh, and Samy Bengio. Learnable fourier features for multi-dimensional spatial positional encoding. Advances in Neural Information Processing Systems, 34, 2021.
  40. 40.Hongzhou Lin and Stefanie Jegelka. Resnet with one-neuron hidden layers is a universal approximator. Advances in neural information processing systems, 31, 2018.
  41. 41.Xuanqing Liu, Hsiang-Fu Yu, Inderjit Dhillon, and Cho-Jui Hsieh. Learning to encode position for transformer with continuous dynamical model. arXiv preprint arXiv:2003.09229, 2020.
  42. 42.Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv:1907.11692, 2019.
  43. 43.Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. arXiv preprint arXiv:2103.14030, 2021.
  44. 44.Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. Advances in neural information processing systems, 30, 2017.
  45. 45.Shengjie Luo, Shanda Li, Tianle Cai, Di He, Dinglan Peng, Shuxin Zheng, Guolin Ke, Liwei Wang, and Tie-Yan Liu. Stable, fast and accurate: Kernelized attention with relative positional encoding. Advances in Neural Information Processing Systems, 34, 2021.
  46. 46.Stephen Merity, Nitish Shirish Keskar, and Richard Socher. An analysis of neural language modeling at multiple scales. arXiv preprint arXiv:1803.08240, 2018.
  47. 47.Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint arXiv:1609.07843, 2016.
  48. 48.Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5115–5124, 2017.
  49. 49.Sharan Narang, Hyung Won Chung, Yi Tay, William Fedus, Thibault Fevry, Michael Matena, Karishma Malkan, Noah Fiedel, Noam Shazeer, Zhenzhong Lan, et al. Do transformer modifications transfer across implementations and applications? arXiv preprint arXiv:2102.11972, 2021.
  50. 50.Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: A fast, extensible toolkit for sequence modeling. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations), pages 48–53, 2019.
  51. 51.Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
  52. 52.Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference on Learning Representations, 2022.
  53. 53.Jack Rae, Chris Dyer, Peter Dayan, and Timothy Lillicrap. Fast parametric learning with activation memorization. In International Conference on Machine Learning, pages 4228–4237. PMLR, 2018.
  54. 54.Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv:1910.10683, 2019.
  55. 55.Hongyu Ren, Hanjun Dai, Zihang Dai, Mengjiao Yang, Jure Leskovec, Dale Schuurmans, and Bo Dai. Combiner: Full attention transformer with sparse computation cost. Advances in Neural Information Processing Systems, 34:22470–22482, 2021.
  56. 56.Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.11198, 2020.
  57. 57.Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pages 593–607. Springer, 2018.
  58. 58.Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pages 464–468, New Orleans, Louisiana, June 2018. Association for Computational Linguistics.
  59. 59.Yu Shi, Shuxin Zheng, Guolin Ke, Yifei Shen, Jiacheng You, Jiyan He, Shengjie Luo, Chang Liu, Di He, and Tie-Yan Liu. Benchmarking graphormer on large-scale molecular modeling datasets. arXiv preprint arXiv:2203.04810, 2022.
  60. 60.Vighnesh Shiv and Chris Quirk. Novel positional encodings to enable tree-based transformers. In Advances in Neural Information Processing Systems, pages 12058–12068, 2019.
  61. 61.Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pages 6000–6010, 2017.
  62. 62.Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
  63. 63.Benyou Wang, Donghao Zhao, Christina Lioma, Qiuchi Li, Peng Zhang, and Jakob Grue Simonsen. Encoding word order in complex embeddings. arXiv preprint arXiv:1912.12333, 2019.
  64. 64.Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396–413, 2020.
  65. 65.Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6861–6871. PMLR, 2019.
  66. 66.Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
  67. 67.Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34, 2021.
  68. 68.Chengxuan Ying, Mingqi Yang, Shuxin Zheng, Guolin Ke, Shengjie Luo, Tianle Cai, Chenglin Wu, Yuxin Wang, Yanming Shen, and Di He. First place solution of kdd cup 2021 & ogb large-scale challenge graph prediction track. arXiv preprint arXiv:2106.08279, 2021.
  69. 69.Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions? In International Conference on Learning Representations, 2019.
  70. 70.Chulhee Yun, Yin-Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. O (n) connections are expressive enough: Universal approximability of sparse transformers. Advances in Neural Information Processing Systems, 33:13783–13794, 2020.
  71. 71.Biao Zhang and Rico Sennrich. Root mean square layer normalization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.

Citation

MLA
Luo, S., et al. “Your Transformer May Not Be as Powerful as You Expect”. Advances in Neural Information Processing Systems, vol. 35, 2022, pp. 4301–15, https://proceedings.neurips.cc/paper_files/paper/2022/file/1ba5f64159d67775a251cf9ce386a2b9-Paper-Conference.pdf.
APA
Luo, S., Li, S., Zheng, S., Liu, T.-Y., Wang, L., & He, D. (2022). Your Transformer May Not be as Powerful as You Expect. Advances in Neural Information Processing Systems, 35, 4301–4315. https://proceedings.neurips.cc/paper_files/paper/2022/file/1ba5f64159d67775a251cf9ce386a2b9-Paper-Conference.pdf
Chicago
Luo, S., S. Li, S. Zheng, T.-Y. Liu, L. Wang, and D. He. 2022. “Your Transformer May Not Be as Powerful as You Expect”. Advances in Neural Information Processing Systems 35: 4301–15. https://proceedings.neurips.cc/paper_files/paper/2022/file/1ba5f64159d67775a251cf9ce386a2b9-Paper-Conference.pdf.
Harvard
Luo, S. et al. (2022) “Your Transformer May Not be as Powerful as You Expect”, Advances in Neural Information Processing Systems. Curran Associates, Inc., pp. 4301–4315. Available at: https://proceedings.neurips.cc/paper_files/paper/2022/file/1ba5f64159d67775a251cf9ce386a2b9-Paper-Conference.pdf.
Vancouver
1. Luo S, Li S, Zheng S, Liu T-Y, Wang L, He D (2022) Your Transformer May Not be as Powerful as You Expect. In: Advances in Neural Information Processing Systems. Curran Associates, Inc., pp 4301–4315

BibTeX

@inproceedings{luo2022your,
  title = {Your Transformer May Not be as Powerful as You Expect},
  author = {Luo, Shengjie and Li, Shanda and Zheng, Shuxin and Liu, Tie-Yan and Wang, Liwei and He, Di},
  year = {2022},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {35},
  pages = {4301-4315},
  url = {https://proceedings.neurips.cc/paper_files/paper/2022/file/1ba5f64159d67775a251cf9ce386a2b9-Paper-Conference.pdf}
}
Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: Published with permission