PaTH Attention: Position Encoding via Accumulating Householder Transformations
Songlin Yang, Yikang Shen, Kaiyue Wen, Shawn Tan, Mayank Mishra, Liliang Ren, Rameswar Panda, Yoon Kim · 2025
Read PaTH Attention: Position Encoding via Accumulating Householder Transformations by Songlin Yang, Yikang Shen, Kaiyue Wen, Shawn Tan, Mayank Mishra, Liliang Ren, Rameswar Panda, Yoon Kim (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-16381.txt.
Introduction
Songlin Yang and co-authors present a new way to encode word position inside language models, in a 2025 paper. Attention alone cannot tell word order, so position must be added. The standard rotary method ties each pair's transform to their gap alone. It ignores the words themselves, which caps what the model can express.
Their scheme, PaTH, builds the position transform from the input. Small reflections, set by each token, multiply as the sequence grows. That makes the encoding data-dependent and more flexible. A compact form of the products allows fast parallel training. Richer position signals could help models track long, structured text where order carries meaning.
Catalog record
| CREATOR | Songlin Yang, Yikang Shen, Kaiyue Wen, Shawn Tan, Mayank Mishra, Liliang Ren, Rameswar Panda, Yoon Kim |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-16381
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
PaTH Attention: Position Encoding via Accumulating Householder Transformations Songlin Yang, Yikang Shen, Kaiyue Wen, Shawn Tan, Mayank Mishra, Liliang Ren, Rameswar Panda, Yoon Kim Abstract The attention mechanism is a core primitive in modern large language models (LLMs) and AI more broadly. Since attention by itself is permutation-invariant, position encoding is essential for modeling structured domains such as language. Rotary position encoding (RoPE) has emerged as the de facto standard approach for position encoding and is part of many modern LLMs. However, in RoPE the key/query transformation between two elements in a sequence is only a function of their relative position and otherwise independent of the actual input. This limits the expressivity of RoPE-based transformers. This paper describes PaTH, a flexible data-dependent p osition encoding scheme based on a ccumulated products of H ouseholder(like) t ransformations, where each transformation is data-dependent, i.e., a function of the input. We derive an efficient parallel algorithm for training through exploiting a compact representation of products of Householder matrices, and implement a FlashAttention-style blockwise algorithm. Across both targeted synthetic benchmarks and moderate-scale real-world language modeling experiments, we find that PaTH improves upon RoPE and other recent baselines. Finally, we show that we can convert pretrained RoPE transformers into PaTH with continued pretraining. † † The implementation of the PaTH attention layer is also made available as part of the FlashLinearAttention library [ 79 , 81 ] : https://github.com/fla-org/flash-linear-attention 1 Introduction Attention mechanisms form the backbone of transformer architectures that power contemporary AI systems. Attention is inherently permutation-invariant, and thus encoding positional information into attention is important for effective sequence modeling. Since the original sinusoidal embeddings [ 77 ] , various position encoding schemes have been proposed over the years [ 16 , 63 , 28 , 25 , 45 , 58 , 72 , inter alia ] ; see Dufter et al. [17] for a comprehensive survey. Among these, rotary position embedding [ 72 , RoPE;] has emerged as the de facto standard, adopted in most recent state-of-the-art LLMs. RoPE works by transforming the key ( {\mathbf{k}}_{j} ) and query ( {\mathbf{q}}_{i} ) embeddings through a rotation matrix \mathbf{R} whose rotation angle is a function of the difference in positions, resulting in the bilinear form {\mathbf{q}}_{i}^{\top}\mathbf{R}^{i-j}{\mathbf{k}}_{j} for the attention logits. The rotation matrix \mathbf{R} itself is a block-diagonal matrix composed of two-by-two rotation matrices, which enables efficient computation. However, the rotation matrix in RoPE is data-independent and only a function of the relative position (i.e., \mathbf{R} applied i-j times), which limits its expressivity; indeed, recent work [ 7 ] demonstrates that RoPE-based transformers are still computationally constrained to the \mathsf{TC}^{0} complexity class, the complexity class of ordinary transformers with absolute position embeddings [ 51 ] . As a potential consequence, RoPE-based transformers have been empirically found to have difficulty with simple synthetic tasks that require a form of sequential reasoning, such as flip-flop language modeling [ 41 ] and certain state-tracking tasks [ 49 ] . Insofar as such simple sequential reasoning underlie real-world capabilities that we want in our LLMs, these failure modes highlight the need to design new primitives that can overcome these theoretical and empirical limitations of existing attention layers. This work develops PaTH, a p osition encoding scheme with a ccumulated H ouseholder t ransformations, targeting the above problem. In PaTH, the attention logit is still parameterized as a bilinear form \mathbf{q}_{i}^{\top}\mathbf{H}_{ij}\mathbf{k}_{j} , but the matrix \mathbf{H}_{ij}\in\mathbb{R}^{d\times d} is obtained via a cumulative product of data-dependent matrices along the path between positions j and i , where the matrices have Householder-like identity-plus-rank-one structure. Intuitively, this formulation captures the cumulative transformation between positions, enabling PaTH to dynamically adapt to input data and solve certain state-tracking problems. Indeed, we show that a constant-layer PaTH-based transformer can solve an \mathsf{NC}^{1} -complete problem under \mathsf{AC}^{0} reductions, i.e., PaTH can extend transformers beyond the \mathsf{TC}^{0} complexity class (assuming \mathsf{TC}^{0}\neq\mathsf{NC}^{1} ). To scale up PaTH Attention, we develop a FlashAttention-like algorithm [ 12 ] for hardware-efficient parallel training that leverages a compact representation of products of Householder matrices [ 5 , 27 ] . Empirical results show that PaTH-based models can solve challenging synthetic state-tracking tasks where RoPE-based Transformers struggle. On moderate-scale language modeling with 760M-parameter Transformers, PaTH outperforms both RoPE and the Forgetting Transformer [ 39 ] , which modulates attention logits via a data-dependent additive term. Combining PaTH with the Forgetting Transformer yields further gains, and the resulting models generalize well beyond the training sequence length. Finally, we show that we can convert pretrained RoPE transformers into PaTH with continued pretraining. 2 PaTH Attention PaTH employs a dynamic data-dependent transition matrix—in particular identity-plus-rank-one Householder-like transformations—for computing the bilinear attention logits, unlike RoPE which applies a fixed transformation at each time step. 2.1 Generalizing RoPE with Multiplicative Position Encodings Traditional additive position encodings, such as sinusoidal embeddings [ 77 ] or ALiBi [ 58 ] , represent positions as vectors or matrices summed directly with token embeddings or attention logits. RoPE instead encodes relative positions multiplicatively rather than additively by directly modulating the key/query vectors via position-dependent transformations. The class of multiplicative positional encodings can more generally be defined as \mathbf{A}_{ij} such that, \displaystyle\mathbf{A}_{ij}\propto\exp\Bigl(\mathbf{k}_{j}^{\top}\Bigl(\prod_{s=j+1}^{i}\mathbf{H}_{s}\Bigr)\mathbf{q}_{i}\Bigr), where i and j are positions of the query and key, and \mathbf{H}_{s}\in\mathbb{R}^{d\times d} is a transition matrix . RoPE is thus a special case of the above with a static transition matrix \mathbf{H}_{s}=\mathbf{R} , where \mathbf{R} is a block diagonal with d/2 independent 2-dimensional rotation blocks, each of which has different rotation angles. This static rotation structure allows for efficient computation of RoPE-based attention in practice. 2.2 Data-dependent Multiplicative Position Encodings with PaTH PaTH employs a data-dependent Householder-like 1 1 1 Householder matrices take the form \mathbf{I}-\frac{2}{\|{\mathbf{u}}\|_{2}^{2}}{\mathbf{u}}{\mathbf{u}}^{\top} and hence our matrix is only Householder-like. matrix with identity-plus rank-one-structure: \mathbf{H}_{t}=\mathbf{I}-\beta_{t}\mathbf{w}_{t}\mathbf{w}_{t}^{T}, where \mathbf{w}_{t}\in\mathbb{R}^{d} and \beta_{t}=2\times\operatorname{sigmoid}(\mathbf{u}^{\top}\mathbf{x}_{t}+b)\in(0,2) are functions of the current input {\mathbf{x}}_{t} . 2 2 2 We use \beta_{t}\in(0,2) as this allows for negative eigenvalues in the transition matrix [ 22 ] , which has been shown to boost the state tracking performance in the DeltaNet case [ 22 , 69 ] . The vector \mathbf{w}_{t} is obtained by applying a low-rank linear layer followed by a short convolution layer (filter size 3) and an L_{2} normalization layer. Hence PaTH only adds a small number of additional parameters. We motivate this parameterization from the perspective of generalizing expressive linear RNNs. Concretely, consider linear attention transformers with matrix-valued hidden states \mathbf{S}_{t}\in\mathbb{R}^{d\times d} with the above Householder-like transition function, where the output ( {\mathbf{o}}_{t} ) given the key ( {\mathbf{k}}_{t} ), query ( {\mathbf{q}}_{t} ), value ( {\mathbf{v}}_{t} ) vectors is given by \displaystyle\mathbf{S}_{t}=\mathbf{S}_{t-1}\mathbf{H}_{t}+{\mathbf{v}}_{t}{\mathbf{k}}_{t}^{\top}, \displaystyle{\mathbf{o}}_{t}={\mathbf{S}}_{t}{\mathbf{q}}_{t}. Recent works have shown that such linear RNNs empirically achieve good performance on language modeling [ 66 , 82 , 78 ] . And despite being more efficient than softmax attention, these models have been shown to be (in a certain way) more expressive than transformers [ 22 , 69 ] , in particular being able to solve a class of state tracking problems that cannot be solved by ordinary transformers. Now consider unrolling the recurrence in the RNN, and compare it against the PaTH-attention output, \displaystyle\text{RNN: }{\mathbf{o}}_{t}=\sum_{j=1}^{t}{\mathbf{v}}_{j}\left({\mathbf{k}}_{j}^{\top}\left(\prod_{s=j+1}^{t}\mathbf{H}_{s}\right){\mathbf{q}}_{t}\right),\hskip 5.69054pt\text{PaTH: }{\mathbf{o}}_{t}=\frac{1}{Z_{t}}\sum_{j=1}^{t}{\mathbf{v}}_{j}\exp\left({\mathbf{k}}_{j}^{\top}\left(\prod_{s=j+1}^{t}\mathbf{H}_{s}\right){\mathbf{q}}_{t}\right), where Z_{t}=\sum_{j=1}^{t}\exp\left({\mathbf{k}}_{j}^{\top}\left(\prod_{s=j+1}^{t}\mathbf{H}_{s}\right){\mathbf{q}}_{t}\right) is the normalizer. This view shows that