Your Transformer May Not be as Powerful as You Expect
Mathematical analysis reveals traditional RPE in Transformers limits universal approximation; proposes URPE to ensure model expressiveness.
Key Findings
Methodology
The authors mathematically demonstrate that common RPE mechanisms, embedded within softmax attention, produce right stochastic matrices which restrict the model’s capacity to approximate all continuous sequence-to-sequence functions. They identify two key conditions—attention structure and position-awareness—that, when satisfied, enable the design of URPE attention. This new module multiplies the softmax matrix with a Toeplitz matrix, breaking the stochastic constraint while preserving efficiency. Extensive synthetic and real-data experiments validate that URPE-based Transformers outperform traditional RPE models in synthetic tasks, language modeling (perplexity reduction from 24.0 to 23.2 on WikiText-103), and graph learning (MAE reduction over 20%). Theoretical proofs and empirical results confirm URPE’s universal approximation capabilities.
Key Results
- The paper proves that standard RPE in softmax attention cannot approximate all continuous functions, highlighting a fundamental limitation. Introducing URPE, which satisfies the two key conditions, transforms the Transformer into a universal approximator. Synthetic tasks show 100% accuracy with URPE, while language modeling experiments demonstrate perplexity improvements on WikiText-103. In graph tasks, URPE reduces MAE significantly compared to baseline models. These results showcase the theoretical and practical superiority of URPE.
- URPE's ability to generalize across multiple tasks confirms its theoretical foundation. It captures positional information more effectively than traditional RPE, especially in long sequences and structured data. The experiments highlight that URPE enhances model expressiveness without adding significant computational overhead, making it suitable for large-scale applications.
Significance
This work addresses a critical theoretical gap in understanding RPE's limitations within Transformer architectures. By establishing conditions for universal approximation, it guides the design of more expressive positional encoding schemes. The proposed URPE mechanism bridges the gap between empirical success and theoretical guarantees, paving the way for more robust, generalizable models in NLP, vision, and graph domains. It offers a new foundation for future research on position-aware deep learning models, with potential to improve long-sequence processing, structural understanding, and multi-modal integration.
Technical Contribution
The paper provides the first rigorous proof that traditional RPE embedded in softmax attention cannot achieve universal approximation. It introduces the URPE module, which multiplies the attention matrix with a Toeplitz matrix, satisfying the two key conditions for universality. Theoretical guarantees are complemented by practical implementations, demonstrating parameter efficiency and broad applicability across tasks. This work combines deep mathematical analysis with engineering innovation, establishing a new paradigm for position encoding in Transformer models.
Novelty
This is the first study to formally analyze the expressive limitations of RPE in softmax attention, revealing its inability to approximate all continuous functions. It proposes a novel URPE mechanism that satisfies the necessary conditions for universality, a significant departure from previous heuristic or purely empirical approaches. The integration of Toeplitz matrices for parameter efficiency and the theoretical proof of universality mark a major advancement in the understanding and design of positional encodings.
Limitations
- While URPE improves expressiveness, its performance in extremely high-dimensional or highly position-sensitive tasks remains to be fully explored. The added parameters, though minimal, may impact training stability in very large models.
- The theoretical analysis assumes continuous functions on compact domains; real-world data may introduce deviations, requiring further empirical validation.
- Future work should investigate dynamic or adaptive position encodings to handle evolving data distributions and longer sequences more effectively.
Future Work
Future research will extend URPE to dynamic, sparse, or learned position encodings, aiming to further improve scalability and robustness. Exploring URPE in multi-modal models, such as vision-language systems, and in ultra-long sequence tasks, will be key directions. Additionally, integrating URPE with efficient training techniques could facilitate deployment in large-scale industrial applications, broadening its impact.
AI Executive Summary
Transformers have revolutionized sequence modeling, yet their ability to encode positional information remains a fundamental challenge. Traditional absolute positional encoding (APE) offers theoretical completeness but struggles with long-sequence generalization. Relative positional encoding (RPE) emerged as a practical alternative, improving performance across tasks like language modeling and graph analysis. However, despite empirical successes, the theoretical limits of RPE within softmax attention were not well understood. This study rigorously proves that standard RPE, embedded as a right stochastic matrix in softmax attention, cannot approximate all continuous sequence-to-sequence functions, revealing a core limitation.
To address this, the authors derive two key conditions—attention structure and position-awareness—that, when satisfied, enable the design of a universal RPE mechanism. They introduce URPE, which multiplies the softmax matrix by a Toeplitz matrix, breaking the stochastic constraint while maintaining efficiency. Theoretical proofs confirm that URPE-based Transformers can approximate any continuous function on compact domains, establishing their universality.
Extensive experiments validate these findings. In synthetic tasks, URPE achieves 100% accuracy, outperforming traditional RPE. In language modeling on WikiText-103, URPE reduces perplexity from 24.0 to 23.2 with minimal parameter overhead. In graph learning, it significantly lowers MAE compared to baselines. These results demonstrate that URPE not only overcomes theoretical limitations but also enhances practical performance across diverse applications.
This work bridges the gap between empirical success and theoretical understanding of positional encoding, offering a new paradigm for designing expressive, efficient, and generalizable Transformer models. Future directions include extending URPE to dynamic and multi-modal settings, further pushing the boundaries of sequence modeling capabilities.
Deep Analysis
Background
Transformers在序列建模中取得巨大成功，尤其在自然语言处理（如BERT、GPT系列）和图结构学习（如Graphormer）中表现优异。早期采用绝对位置编码（APE）以增强模型对序列位置的感知，但在长序列泛化能力方面存在局限。相对位置编码（RPE）逐渐成为主流，因其在长序列和多模态任务中的优势，诸如Shaw、T5和Transformer-XL等模型验证了RPE的实用性。然而，关于RPE的理论表达能力尚未充分研究，尤其在softmax注意力中其限制未被揭示。
Core Problem
尽管RPE在实践中表现良好，但其在理论上的表达极限未被明确。特别是在softmax注意力中，RPE输出为右随机矩阵，限制了模型捕获复杂位置关系的能力。已有研究表明，传统RPE不能逼近所有连续函数，存在本质缺陷。这限制了模型在复杂任务中的泛化能力，亟需设计具有理论保证的增强机制。
Innovation
本文的创新点包括：1）严密数学证明传统RPE在softmax注意力中不能实现泛化，揭示其局限性；2）提出满足两个关键条件（注意力结构和位置感知）的URPE机制，突破随机矩阵限制；3）引入Toeplitz矩阵参数化，保证参数效率和泛化能力。这一设计结合理论分析与工程实现，为位置编码机制提供新范式。
Methodology
- �� 分析softmax注意力输出为右随机矩阵的数学性质，证明其限制模型表达能力；
- �� 提出两个条件：注意力结构（包含特定attention形式）和位置感知（能区分不同位置）；
- �� 设计URPE机制，将softmax矩阵乘以Toeplitz矩阵，满足上述条件；
- �� 通过理论证明URPE满足泛化条件，确保模型成为泛化的函数逼近器；
- �� 在synthetic、语言和图结构任务中验证URPE性能，比较与传统RPE的差异。
Experiments
在synthetic任务中，URPE模型实现100%准确率，验证理论。语言建模中，困惑度从24.0降至23.2，参数几乎不变。图学习中，MAE降低20%以上。多任务验证显示URPE在长序列和结构化数据中表现优异，验证其理论优势。实验结果充分证明URPE在实际场景中的优越性。
Results
URPE模型在synthetic任务中实现完美逼近，验证了理论分析。在WikiText-103中，困惑度提升显著，参数效率高。图学习中，MAE显著降低，优于基线模型20%以上。多模态任务中，URPE展现出更强的泛化能力，突破了传统RPE的限制。
Applications
该机制适用于自然语言处理、图结构分析、多模态学习等场景，尤其在长序列和复杂结构数据中表现优越。未来可结合稀疏、动态位置编码，提升大规模模型的泛化和训练效率。
Limitations & Outlook
模型在极端位置敏感任务中仍存在不足，参数调优和训练稳定性需优化。理论分析假设连续函数，实际应用可能存在偏差。未来应结合实际任务进行调优和模型简化。
Plain Language Accessible to non-experts
想象你在一个工厂里，工人们需要按照不同的顺序完成任务。传统设计只给每个工人编号，比如1、2、3，但如果任务很复杂，编号可能不够用。于是，工厂引入了相对位置的概念，比如“这个工人在前面几个步骤”，这样更灵活。现在的问题是，有些工厂的设计（比如用softmax注意力）会限制他们只关注“绝对编号”，不能理解“相对距离”。这就像工厂的机器只能看见编号，不能看见工人之间的距离。作者发现，这样的设计不能完成所有任务，特别是那些需要非常精确位置关系的任务。于是，他们设计了一种新机器（URPE），可以同时看见编号和相对距离，就像给工厂装上了更聪明的传感器。经过测试，这种新设计能完美完成复杂任务，比传统设计更强大。它不仅能用在语言处理，还能用在图像和结构数据中，让人工智能变得更聪明、更懂“位置”。
ELI14 Explained like you're 14
想象你在学校，老师布置了很多任务。有时候，老师告诉你每个任务的编号，比如第1、第2，但有时候会告诉你任务之间的距离，比如“这个任务比那个早几个步骤”。如果只记编号，可能会忘记任务的关系，但如果知道相对距离，就能更好安排顺序。现在，很多智能程序（像Transformer）也是这样，用一种叫位置编码的方法记住任务顺序。以前的方法只用编号，但研究发现只用编号不能让程序学得更复杂。于是，科学家们设计了一种新方法，既记住编号，也记住任务之间的相对距离，就像给程序装上了“聪明的眼睛”。这样，程序就能更好理解长句子、复杂图形，表现得更棒。这让人工智能变得更聪明、更灵活，就像你学会了更聪明的学习方法一样。
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.