PaTH Attention: Position Encoding via Accumulating Householder Transformations
Authors: Songlin Yang
Yikang Shen
Kaiyue Wen
Shawn Tan
Mayank Mishra
Liliang Ren
Rameswar Panda
Yoon Kim
Venue: NeurIPS 2025 poster ()
Keywords: position encoding
state tracking
position embedding
contextualized position encoding
sequence modeling
softmax attention
attention mechanism
DeltaNet
delta rule
Primary area: deep_learning
TL;DR: We propose a contextualized position encoding using dynamic Householder matrices in place of static rotary ones, along with a hardware-efficient training algorithm that improves state tracking performance.

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 position encoding scheme based on accumulated products of  Householder(like) transformations, 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.

PaTH Attention: Position Encoding via
Accumulating Householder Transformations
Songlin Yang'
Yikang Shen Liliang Ren
Kaiyue Wen
Shawn Tan
Mayank Mishra
Rameswar Panda-
Yoon Kimè
Massachusetts Institute of Technology
MIT-IBM Watson Al Lab
Stanford University
Mierosoot
yangs1660mit.edd
Abstract
The attention mechanism is core primitive in modern large language models (LLMs) and Al more broadly. Since attention by itself is permutation-invarian position encoding is essential for modeling structured domains such 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 sequence only a function their relative position and otherwise independent of the actual input. This limits the expressivity RoPE-based transformers. This paper describes PaTH, a flexi- ble data-dependent position encoding scheme based accumulated products of Householder(lik)) transformations, where each transformation is data-dependent, i.e., function of the input. We derive an efficient parallel algorithm for training through exploiting a compact representation of products of Householder matri- blockwise algorithm. Across both
ces, and implement FlashAttention targeted synthetic benchmarks and moderate-scale real-world language modeling experiments, 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.
Introduction
Attention mechanisms form the backbone of transformer architectures that power contemporary AI systems. Attention is inherently cemmutation-ivariinn, 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]; Dufter al. [17] for comprehensive survey. Among these, rotary position embedding [RoPE; 72] has emerged as the de facto standard, adopted in most recent state-of-the-art LLMs.
RoPE works by transforming the key (k,) ) and query (q.) embeddings through rotation matrix R whose rotation angle is a function the difference in positions, resulting in the bilinear form q. R'-ik, for the attention logits. The rotation matrix R itself is block-diagonal matrix composed of two-by-two rotation matrices, which enables efficient computation. However, the rotation matrix in RoPE is data-inat iitta-nddeeenennt and only function of the relative position (i.e., R applied which limits its expressivity; indeed, recent work [7] demonstrates that RoPE- based transformers are still computationally constrained to the TC complexity class, the complexity class of ordinary transformers with absolute position embeddings [49]. As potential consequence, RoPE-basee transformers have heen empirically found to have difficulty with simple synthetic tasks that require form of sequential reasoning, such as flop-flop language modeling [41] and certain state-tracking tasks [51]. Insofar as such simple sequential reasoning underlie real-world capabilities that we want
times),
The implementation of the PaTH attention layer also made available as part of the FELASHLNNEAAATTENTII library (80, 79]: https:/ //ggt/gg.....t/t// cwt.u....oo///i/. hommflllorg//// fls/hlaahhhaeeee linear- attention
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

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 position encoding scheme with accumulated Householder transformations, targeting the above problem. In PaTH, the attention logit is still parameterized as a bilinear form 9: Hijky. but the matrix Hij E idxd is obtained via a cumulative product of data-dependent matrices along the path between positions and where the matrices have Houscholder-like
structure. Intuitively, this formulation captures the cumula- tive transformation between positions, enabling PaTH dynamically adapt to input data and solve certain traekira problems. Indeed, we show that a constant-layer Pa PaTH-Ba based transformer can solve an NC -complete problem under AC reductions, i.e., PaTH can extend transformers beyond the TC complexity class (assuming TC * NC²).
To scale up PaTH Attention, develop FlashAttention-likk algorithm [14] for hardware-efficient parallel training that leverages 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 yiclds 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 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 sinusoidal embeddings [77] or ALiBi [58], represent positions 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 bssition-deendeen transformations. The class of multiplicative positional encodings can more generally be defined as Ai such that,
Aij exp exp(k; k3
(II H. H.).)). +=++1
where and j are positions of the query and key, and H, E [R. a transition matrix. RoPE thus special case of the above with a static transition matrix H, R., where R. is 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-lic matrix with identity- contity-plus rank-one-structtre:
H, = -I- 3.w.w?"
where w, e IRd and B, 2 sigmoid(u" x; + b) e (0,2) are functions of the current input x,.² We motivate this parameterization from the perspective of generalizing expressive linear RNNs.
Concretely, consider linear attention transformers with valued hidden states S, Rdxd with the above Householder- like transition function, where the output (o,) given the key (kt), query (qp), value (v,) vectors is given by
S. = S H v,k,
O, = =S.
Householder matrices take the form Tolz uu and hence matrix only Householder-like.
"W use 8, E (0,2) this allows negative eigenvalues shown to boost the state tracking performance in the DeltaNet case [22, 69J. The vector w. is obtained by applying low-rank linear layer followed by short convolution layer (filter size 3) and an La normalization layer. Hence PaTH only adds small number of additional parameters.
transition matrix [22], which has been

---

Recent works have shown that such linear RNNs empirically achieve good performance on language modeling [66, 78, 82]. 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,
2
(
2 H.
RNN: =
V3
kj
II
H
q:
PaTH: Or Zz
E exp
kj
III La-f+1
q0
jm1
where 2, = Ej= exp K (Ti=ztt1 H qt) is the normalizer. This view shows that PaTH is
closely related to such expressive linear RNNs, and we thus expect PaTH-based transformers to inherit their increased expressivity. Indeed, the following theorem shows that PaTH can extend transformers beyond the TC complexity class.
Theorem 2.1. A one-layer PuTH transformer with two attention heads and log precision can solve an NC¹ -complete problem under -reducttts.
The proof, given in appendix A, is straightforward adaptation of Theorem 2 from Peng et al. [56], which showed the that linear RNNs with a similar data-dependent transition matrix can solve an NC' commleete problem. However, such RNNs still have theoretical limitations that attention does not have, for example in its (in)ability to perform associative recall over given context of arbitrary length [2]. contrast, PaTH can capture the benefits of both softmax attention (associative recall) and expressive linear RNNs (state tracking).
Extension: PaTH-FoX. PaTH simply provides a more expressive way to encode unnormalized attention logits and is thus compatible with other recently proposed modifications to softmax attention such Stick-Breaking Attention [73], Selective Attention [35], and Forgetting Transformer [FoX; 39]. As case study we experiment with combining PaTH with FoX, which additively modifies the attention logits in date-dependent manner. We show that this combined strategy leads to improved performance on some downstream tasks, especially in length extrapolation.
Concretely, FoX [39] modifies the attention via detendepe "forget" gates f. E (0,
Elog -(I
A.j exp kj q
log
II +=++1
exp k) a:)
A=++1
where fa (igmoid(u].. x, + by). Similar to how PaTH can be seen as softmax version of DeltaNet-style linear RNNs [65, 81), FoX can be seen as softmax version of GLA-/Mamba2-style linear RNNs [80, 13).² We can combine the two mechanisms to arrive at PaTH-FoX attention:
Ag x
5. exp kj II
H.
H. 9:
We found this variant to be quite effective language modeling, reminiscent of the improvements observed by combining DeltaNet with Mamba2 [Gated DeltaNet; 82) in the linear attention case.
Efficient Training and Inference for PaTH Attention
Efficient kernels for attention [14, 12, 68] work by operating subblocks of query and key matrices to avoid materialization of the full attention matrix in slower DRAM. Unlike RoPE however, the cumulative products II, H, in PaTH are function of the input and thus it is not clear whether PaTH- attention computations can similarly be decomposed into computations over subblocks. We now describe how the cumulative product of Houscholder' transformations can be efficiently computed using a compact representation of Householder products [27] and applied in a blockwise fashion [76, 47, 48, 81] derive PlashAttention-lik algorithm that integrates blockwise Householder transformations with blockwise attention computations.
'However, this analogy is not quite as crisp the Mamba2- -Fo case. Mamba2 uses the recurrence S. -.S.-1 + vek, and unrolling this would give = E/= (II' f.) kj q Applying softmax on this would give o, J.2 E vy (IT== fa kJ k.):) which is different from FoX where the I fa term is outside the exponential function. In preliminary experiments we found this softmax version Mamba2 to greatly underperform FoX.
WWe hereon abuse terminology and use "Householder" refer Householder-Hie transformations.
3

---

3.1 Background & Notation
We denote the block size along the sequence length dimension as B and define subblocks using the notation A [+).b)] == (BBB( E Bx This notation extends analogously to the other blocks X [ X 1)) RBxx for X (Q. K. V, W. O), where (for example) W(j) obtained from the vectors w.n..... ()+ in the Householder transformations.
FlashAttention. FlashAttention uses the online softmax trick [52, 61] to compute the output matrix O block by block. For each query block it sequentially process the key/value blocks j from 0 to i, computing and accumulating the output as follows:
exp O K
if <j =
B
Ol
Σ J=0
AL V E Bxd
exp (lower Qu K (())
The attention submatrices A [AG are computed and processed entirely within SRAM, eliminating the need write them to slower DRAM, which greatly reduces I/O costs and results in wallclock- speedups. Our algorithm also performs computations of the output block by block, but takes into account the additional contributions from data-dependent Householder transformations.
UT transform for products of Householder matrices. major challenge in computing PaTH attention lies in handling products of Houscholder matrices. We adopt the UT transform [27] to address this efficiently. For a sequence of transformations H, = w. their product can be compactly expressed as:
P:
H. -1 W T '
E 1xd
where
= (I strrictLooe -1 DD
E R Lx1
Here, W - WL-1] T R.xd D .2-,1........) E RLL We abuse notation for T-1 here for incorporating D to avoid notational clutter. The UT representation is efficient on modern hardware due its use of triangular solves and matrix products [76], and is often preferred over alternatives such as the WY transform [5, 67].
3.2 Full Matrix Form of PaTH Attention
Recall that in PaTH attention, the attention score is given by Air x exp (k] [Ilişt+1 H. qi
which involves cumulative product over arbitrary intervals 1, naive implementation would require recomputing the UT transform for each such interval, which is computationally intractable. However, we show that it is possible to reuse the global matrix inverse T and apply simple masking to efficiently extract the product over any subinterval.
To represent the product masked U'' transform:
interval co
H, (with start index so and end index eq), we the
II -H (W M T ( M
where denotes element-wise multiplication. The binary masks ML sp. entrywise as:
M E RRdd are defined
{ 0
if N sp, otherwise,
{o
if < eo. otherwise.
(M
(M kc
(M
Then, we have:
À, kj
II H.
q K]
kJ.w M/ Mf)q
t=j+1
and equivalently, in matrix form:
Ā = lower(QK') - lower (QWT) T-1 strictLowerrWWE) (WKT)

---

This decomposition enables efficient pairwise attention computation using shared UT structure and interval-specific masking. However, computing the global inverse T incurs prohibitive (I))) time complexity with respect to sequence length J. In the following section, we introduce blockwise algorithm that obtain the same result using only local inversions, thereby reducing the overall complexity match that of standard attention mechanisms.
3.3 Efficient Training
To enable hardware-efficient (blockwise) training, cumulative Householder transformations must be pre-applied to the left and right boundaries each block; otherwise, the token-specific nature of these transformations would render blockwise computation infeasible. To this end, we define boundary-adjusted query and key matrices follows:
(Q))
II
Hm
qiBtt 9:++ W
(W() ④ M. Mq
E Ie"
(++1))
(K())=
II mm38-411
Hm
kiB+s ki
(T W(4) (Wia @ K.B-
a following the derivation in $3.2. In matrix form, these can be expressed as:
[
Q
lower Q W
W
E IR Rxd
K
strict W
K()
WH
E RR Bxd
With these quantities, we express the attention block computation as:
exp
m=
P
K 1d]
ifi> J. E RB
A (1.D
exp
Q K
lower
Q14
T i strictLower W1a
if if j
where P ==
I1
H.B+j
WE E
Raxd
Due to associativity, the cross-blos block term
can be computed incrementally: O
P((m))
K Dj ((( JP
1 b)
We adapt the FlashAttentioon-sylle block processing framework perform right-to-left scan over key/value blocks, enabling this product accumulation in streaming manner. Concretely the modified blockwise workflow for processing query block as follows:5
Load Q into SRAM.
For key/value blocks = 1,,-,,.... 1,..., (right-to-left scan):
Load K Vo and Pt from HBM into SRAM.
Compute logits: A Q K
Update online softmax statistics and accumulate output as in FlashAttention.
Update query: Q a) + Q
P
Normalize and store the output HBM as in FlashAttention.
This design preserves the I/O efficiency of FlashAttention while incorporating PaTH's dynamic positional encoding via streaming cumulative products.
Complexity analyses. For each head, the attention computation between a pair of query and key blocks takes O Bd) time-O(B2d)) for computing attention scores and O(Bd for
DDifferent query blocks can be executed in parallel, following context- context-parallel strategy similar to that of F [12].
5

---

applying the transition on queries. Since there are (L/B)² such block pairs, the total attention cost is O(L'd LB) For preprocessing, computing the local Householder-bace
transformation for each query/key block involves an inversion step with cost O + d²d). With T. such blocks, d (which is often the case), the overall complexity is comparable to standard attention, with quadratic scaling in sequence length.
the total preprocessing cost is O + I.Bd). When
Speed Comparison. We implement the PaTH attention ker- nel' in Triton [75] and benchmark its runtime on single H100 GPU against FoX and standard RoPE attention under identi- cal settings: batch size 32, 32 heads, head dimension 64, and varying sequence lengths. Results are shown in Figure 1. PaTH incurs modest slowdown compared to RoPE, but outperforms
PaTH-triton
700
Flashattention-trioo
Execution Time (ms)
Fox-triton
500
400-
FoX. Further speedups are expected from future kernel-level optimizations (e.g., via ThunderKittens [71]).
300-
200
3.4 Efficient Inference
100
We can efficiently update historical keys in-place using the current timestep's transition matrix:
4K
8K
16K
Sequence Length
k. + (I - -,,w.,, B.w.w])k((t)) [k(-1) for all i (I)
Figure 1: Speed comparison between
where k!d) k, This in-place update strategy eliminates attention variants.
the need to store a separate cache for [wilise or recompute the somewhat expensive cumulative Householder transformations. Then, the decoding stage becomes equivalent standard softmax attention decoding, enabling compatibility with existing inference kernels such as FlashDecoding [15] and Paged Attentitonionn [34]. This approach maintains inference efficiency while preserving PaTH's dynamic positional encoding capabilities. Similarly, FaTH-FoX can be reduced to FoX decoding and thus compatible with the acceleration techniques of FoX (e.g., adaptive pruning [40]).
Before decoding, the initial key representations k, must be transformed to k. to account for subsequent Householder transformations. This transformation could be computed blockwise as:
P PPI//BII
[4]
It is also possible to reuse the suffix cumulative product P P[tt)]-. (ery)a..PPPyy across blocks reduce the overall complexity to linear.
3.5 Discussion
Compatibility with context-paree context-parallelism (CP) techniques. To extend our FlashAttention2-styll context-parallel strategy to distributed settings such as Ring Attention [43, 38), PaTH's cumulative
Householder transformations must be aligned with the ring-based key/value (KV) passing mechanism.
Each device first precomputes its locally transformed queries (Q) and keys (K) by applying its resident Householder transformations. This also yields the local Householder product matrix ((d) and softmax statistics for its sequence chunk. During inter-device communication, each device transmits its transformed
K vectors (with V) and the associated ((d) to the next device in the ring.
Upon receiving a (K, V, v(d)) tuple from an earlier segment, the query-holding device first computes attention outputs using its current Q and the incoming (transformed) keys, accumulating both the output and the corresponding online softmax statistics like standard attention. It then updates its <- Q in-place via Q T propagating the cumulative path transformation forward along the ring. This sequence- compute output with current state, then update query state via incoming faithfully emulates PaTH's logical right-to-left scan, enabling correct path reconstruction across distributed segments.
Iterative refinement of KV cache. From equation 1, PaTH iteratively applies low-rank updates to the historical key cache, forming a cumulative product of deentty-plus-low-ratt terms in the attention logit computation. This dynamic modification of the key cache is conceptually intriguing; see Song et al. [70], Ewer et al. [18], Leviathan al. [35] for related ideas. Future directions include
'nttps://githin www./oa-oooo/eeeo wwt.///ooooo//lllaealllloooooeee linear- wtw.a//ettaattii///e/ee/aaa//aaa
attn

---

(i) extending this update mechanism to refine value vectors and (ii) developing more expressive yet hardware-efficient KV cache refinement schemes beyond the low-rank formulation used in PaTH.
4
Experiments
Method
ID
OOD
We experiment with PaTH attention and compare it against various baselines: ordinary RoPE attention, Stick-Breaking Attention (SBA) [73], and Forgetting Transformer (FoX) [39].
Sparse
Dense
RoPE
6.9%
40.3%
0.01%
SBA [73]
9.6%
38.9%
0%
4.1 Synthetic Tasks
FoX [39]
8.3%
36.3%
0%
PaTH
0%
0.0001 %
0%
Flip-flop language modeling. We first experiment with fli- flop language modeling (FFLM) [41], diagnostic synthetic task which has been found to be challenging for existing ar- chitectures. In this task, the vocabulary consists of Σ {w, i, 0, 13. Given a sequence of write-bit, read-bit, ignore-bit actions, the model must produce the bit (0 1) after the most recent write-bit action. For example given the sequence "w r O 1 i i r", the model is expected to recall the most recently written bit, i.e., O. De- spite its simplicity, flip-flop language modeling is diagnostic of many real-world capabilities, such as modeling long-range dependencies, the ability to ignore distractors, and sequential reasoning. Liu et al. [41] find that RoPF-based transformers struggle on this task and provide theoretical insights into why RoPE-based attention mechanisms find it inherently difficult. In Theorem A.I of the appendix we show that there exists a 2-layer PaTH-based transformer that can solve this task. Empirically, our experiments in Table show that PaTH-based transformers can practically learn to almost perfectly solve this task with only a single layer and two attention heads, including out-of- distribution settings whose frequency of operations are different from than in training (sparse means 98% of the operations are ignore, while dense means only 10% ignore).
Table 1:
FFLM enror rate (%) on
ID/OOD test sets. All models are layer, 2-head, 64-dim.
MQRAR
Accuracy
1.0
0.0
N-back
Min. of Layers
A5
3
2-
1
10
15
Sequence Length
FoX
Stick-Breaking
PaTH
RoPE
Figure Results on MQRAR-N (top) and A5 word problem (bottom).
Word problems. We showed in $2.2 that PaTH can theoretically extend transformers beyond TC² However, it is different question as to whether PaTH transformers can empirically learn to solve NC NC'mcomelete problems based on actual data. To test this, we follow Merrill et al. [51] and use word problem task based on the alternating group As, subgroup of S; (on which the word problem is also NC ccmmppeee, This task requires determining if "word"-a sequence of group to the identity element. Successfully
operations using fixed generators and their inverses-evally performing this symbolic task means the model must implicitly learn algebraic rules like permutation composition and cancellation. As a concrete example, consider generators 91 = (1 3), 92 = (12 2). and 93 = (1 5).. 5). with their respective inverses 91 92 93 Given the word w = 91 21-92 92 91 992 the model must determine
equals the identity permutation. In this instance, w is not the identity, and the model needs to correctly track the sequence of permutations to arrive at this conclusion. Figure 2 (bottom) shows that PaTH can solve this task defined as achieving above 90% acciracy following Merrill et al. [51]) with fewer layers than baselines.
Multi-query Repeated Associative Recall with N-back (MQRAR-N). We adapt the Multi-query Repeated Associative Recall (MQRAR) task from Tan et al. [73] (itself an enhancement of MQAR [1)) to HQRAR-N-bacc. This task tests a model's s associative recall ability by requiring it to find the
N-th last assignment for given variable, drawing an analogy to the N-back task in experimental psychology [30]. Recalling the most recent assignment (N = 1) can often be accomplished by simpler, recency-focused mechanisms. However, retrieving the --th last assignment (N > more rigorously probes model's 's capacity to track an ordered history of states for specific variables, especially when recent information must be ignored. An example sequence for N is:
Input Output
B
C
D
4
B
A
7
C
A
0
0
0
0
1
6
5
6
7

---

We compare Transformer models using RoPE, SBA, FoX, and PaTH on their ability to handle MQRAR-N-bach with N E 2,, 4). All models are 2-layer Transformers with 256-dimensional hidden state, 2 attention heads. For the task we use 32 key-value pairs sequence length of 768. Figure shows the results, where we find that PaTH attention can successfully track variable values with N-back recall for N < 4, whereas recent baselines (SBA and FoX) still struggle.
4.2 Language Modeling
We pretrain language models with 760M parameters on the Fineweb-Fin Edu corpus [54] for 50B tokens using the Mistral tokenizer and a sequence length of 4096. We then evaluate the pretrained models on the following benchmarks. See appendix B for full details and additional experiments.
Model
Wiki ppl
LMB.
LMB.
PIQA
Hella.
Wino. acc f
ARC-e acc f
ARC-c acc_mi t
Avg. f
ppl 4
acc
acc f
acc n f
RoPE
19.01
19.77
40.4
70.2
50.3
54.9
67.2
33.3
52.7
FoX
18.33
18.28
41.7
70.8
50.9
57.1
65.7
32.6
53.1
PaTH
18.03
16.79
44.0
70.5
51.5
56.0
68.9
34.4
54.2
PaTH-FoX
17.35
16.23
44.1
70.8
52.2
57.1
67.3
33.9
54.2
Table 2: Results on perplexity and zero-shot commonsense reasoning tasks for 760M models trained on 50B tokens. Best results are highlighted in bold, while the second hest results underlined.
Standard LM benchmarks. We evaluate on Wikitext perplexity and selected zero-shot common sense reasoning tasks, including of LAMBADA [LMB.: 53] (OpenAl version), PiQA [6], Hel- laSwag [Hella.; 83], WinoGrande [Wino.; 64), ARC-easy (ARC-e) and ARC-challenge (Are-c) [10]. Table 2 shows the results. PaTH consistently outperforms RoPE across all tasks, and surpasses FoX on most. PaTH-FoX performs comparably with PaTH while achieving the lower perplexity.
Length extrapolation. Figure 3 presents results on three long-context corpora from different domains: PG-19 [62] (books), CodeParrot (code), and NarrativeQA [31 [conversational English). Both PaTH-FoX and FoX generalize up to 64K tokens, with PaTH--oX consistently achieving lower perplexity. The improvement is especially pronounced in the code domain, where state tracking-ed tracking variable values is crucial. PaTH alone generalizes reasonably well, maintaining stable performance up to 32K tokens, after which perplexity gradually increases (in contrast to RoPE, which fails abruptly beyond 4K). These results underscore the benefit of data-dependent position encoding and the critical role of the forgetting mechanism in enabling robust generalization to longer contexts.
CodeParrot
PG19
Narrative QA
20
30
30
Perplexity
15
Perplexity
25
Perplexityy
25
10-
20
20
15-
10
10
1K
22K
43K
64K
1K
22K
43K
64K
1K
22K
43K
64k
Token position indices
Token position indices
Token position indices
FoX
PaTH-FoX
PaTH
RoPE
Figure 3: Length extrapolation results for 760M models trained on 50B tokens with 4096 context length.
Long-context benchmarks. Table summarizes results on four challenging long-context bench- marks: RULER [23], BABILONG [33], PhoneBook [26], and LongBench-E [3]. For RULER, we report the zero-shot average accuracy across all 13 subtasks and also breakdowns by task categories and context length in Figure 4; for BABILONG,
follow standard practice and report the average few-shot accuracy over subproblems DA0-QA5 (see Figure for breakdowns by task and context length); for LongBench-E, we report average scores across three length intervals 0 4K, 4 4-8K, and 8-16K-and provide detailed results in Table 7.
These benchmarks assess different aspects of long-context understanding. Accurate re- trieval is critical and is tested by RULER's Single- and Multi- Needle-In-A-Haystack (NIAH) tasks, well as by PhoneBook Lookup, an extreme case where every token in the context is a 'needle". PaTH-FoX achieves the highest overall re- trieval performance, excelling in the more difficult Multi-NIAH and PhoneBook settings.
8

---

Single-NIAH
Multi-NIAH
Aggregation
Variable Tracking
0.6
0.4
Accurary
0.6
Accuracy
4
Accuracy
0.3
Accuras CCC
0.4
0.2
0.1
0.0
0.0
8K
0.0
4K
0.0
Sequence Length
Sequence Length
Length
Sequence Length
Fox
PaTti-FoX
-
PaTH
.
RoPE
Figure 4: RULER results grouped by different task categories.
Model
RULER
BABILONG 4K
PhoneBook
LongBench-E 8K
4K
8K
16K
0K
8K
16K
2K
4K
8K
4K
16K
RoPE
35.7
1.3
0.0
33.0
13.8
0.0
0.0
32.3
15.6
0.0
18.7
3.7
2.0
FoX
41.6
29.5
4.9
23.8
20.2
8.2
4.4
62.5
38.5
17.7
23.4
16.9
11.7
PaTH
44.6
34.8
18.7
33.8
24.6
16.8
11.6
55.2
20.8
0.0
27.2
22.5
14.4
PaTH-FoX
42.3
34.0
22.6
28.6
25.6
19.2
10.0
89.6
93.8
66.6
23.4
21.8
16.1
Table 3: Summary of average scores on long-context tasks for 760M models with training length 4096.
Beyond retrieval, RULER also probes state track- ing through its Variable Tracking (VT) task.? РaTH and PaTH-FoX achieve substantial gains here, consis- tent with their advantages synthetic kate-tracking tasks. BABILONG further tests such capabilities in a narrative setting, embedding bAbl-style logic queries within long PG-19 passages- passages-thus tity tracking and multi-hop reasoning text. On these tasks as well, PaTH and PaTH-FoX clearly outperform FoX and RoPE.
Model
GSM8K
HumanEval
MBPP+
RoPE
19.9
23.1
47.1
FoX
15.5
21.3
48.2
PaTH
20.1
25.6
51.3
Basc
8.6
16.4
38.6
thus requiring both en- extended
Table Results on math and coding benchmarks after conversion. Base denotes the teacher model performance before continued pretraining.
4.3 Converting RoPE into PaTH
Training LLMs from scratch is highly resource-intensive. We hence explore con- verting pretrained RoPE-based L.LSs into PaTH-hased I.LMs, particular targeting improvements in math/coding domains.
Task
Teacher (RoPE)
Student (PaTH)
MMLU
74.21
73.28
HellaSwag
85.20
84,83
Winogrande
71.51
68.90
GPQA Diamond
33.33
34.34
Following Goldstein al. [20], we use two-stage distillation process first minimizes the Mean Squared Error (MSE) between the attention-lave layer outputs of the RoPE teacher and the PaTH student, followed by fine- wning using KI. divergence on the outputs. The first and second stages use 100M and tokens, respectively, from the DCLM corpus [37]. After distillation, we perform continued pretraining using a balanced mixture (1:1:1) of DCLM (text), Python-Edu (code), and MegaMath Web (math) corpora [87] of 21B tokens. Since it may be diffieult to observe sizeable improvements over existing (often overtrained) state-of-the-art models that have already been exposed to extensive math/coding data, work with the SmolLM2-1. 7B checkpoint taken immediately before the WSD decay stage [24], i.e., prior to exposure to high- quality math and code data. As shown in Table 4, PaTH consistently outperforms both RoPE and FoX. We speculate that PaTH's expressivity and state-tracking capabilities contribute to its advantages in handling math and coding tasks.
ThcoremQA
18.12
21.88
GSM-8K
80.29
80.67
MATH
69.10
65.38
HumanEval
82.32
77.44
MBPP
74.71
75.10
RULER (4K)
94.37
93.24
Table S: Qwen2. 5--n2,.-7B-Inae Insttrutt distillation results (with- out continued pretraining on math/code data).
While the above results are promising, we find mixed results when distilling from models that have already been extensively (over)trained. Table 5 shows the performance when distilling Qwen2. 1wee2.557B--. the teacher's performance across some benchmarks, but there is degradation across others. These
[60] without the continued pretraining stage: PaTH student can improve
E.gg. given "VAR X1 12345, VAR X2 3212, .... VAR X10 X1, ... the query might ask "Find all variables assigned the value 12345", with the correct answer being "X1, x10". 'nttps:/huuglngfface wtteaacc...ooooeeeeeeeeeeeee http//gggigaaaee///SSntana SmmlLLN-nanotroo pre-decay
nanotron teppt/tree/mann//

---

distillation experiments suggest that it may be important to start the conversion process before the original model (potentially) ossifies and becomes difficult to convert; better conversion recipes remain an avenue for future work.
5 Related Work
Data-dependent positional encoding. RoPE [72] has been the de facto position encoding scheme in large language models. However, RoPE's static nature makes it unsuitable for dynamically adapting to long sequences, motivating works on RoPE length extension [55, 8, 44, inter alia]. Yet, these methods remain within the RoPE framework and only mitigate rather solve its limitations. An alternative line of work focuses on data-dependent position encoding. While promising, these approaches operate solely the attention logit level, modifying the QK scores through post hoc transformations [85, 39, 86, 21, 35, 73, 11]. However, the dot-product structure is fundamentally limited in its ability to represent more intricate dependencies [19, 32], motivating work on algebraic position encodings [32], where relative positions are encoded via cumulative matrix products. While conceptually similar to our approach, APE focuses exclusively on data-indlpeendent orthogonal (and thus invertible) matrices that are simultaneously diagonalizable [59], and thus inherently limited in expressivity [9, 51, 74]. In contrast, our proposed PaTH method addresses this limitation by using data- data-dependent cumulative Householder-lik products, which are non-invertible non-commutative, and not simultancously diagonalizable, leading to more expressive transformations of the unnormalized attention logits. Moreover, PaTH is compatible with other attention variants, such as FoX, providing a principled and extensible framework for positional encoding.
Improving state tracking in language models. Transformer-based language models often struggle with state and entity tracking [29, 57, 51]. This is potentially due to the standard transformer architecture's finding it difficult to reliably emulate finite-state automata [41, 42, 88, 4]. To shed light on the theoretical reasons transformers struggle with word problems (tasks requiring careful state tracking). recent studies have analyzed their learning dynamics [36] and conducted mechanistic investigations [84]. Researchers have also proposed alternative attention mechanisms enhance self-attention's 's expressivity. These aim to capture richer pairwise dependencies than standard dot- product attention, often by incorporating lightweight recurrence such as right-to-left cumulative sums into the attention logits [21, 35, 73]. Fagnou et al. [19] propose matrix ieriiiiiivviiin--ee based attention mechanism for capturing path-level dependencies, which conceptually similar to our approach. While these methods show empirical improvements in state or entity tracking tasks, they are largely heuristic. In this work, we draw inspiration from theoretical studies on parallelizing RNNs while preserving their state tracking capabilities [51, 22, 69, 56). From these, we design a new softmax- attention mechanism that is performant and efficient.
Limitation
While PaTH improves expressivity, it has several practical caveats. Training stability can be sensitive to numerical precision. In particular, the cumulative product of Householder transformations may become unstable under BF16, requiring clipping of the scaling factor 3 to prevent it from reaching 2, as BF16 rounding can otherwise produce eigenvalues larger than I and cause divergence. In addition, the speed comparisons in this work are restricted to head dimension 64. Larger head dimensions increase the computational and memory overhead of PaTH. Finally, PaTH does not directly model rotations, single reflection matrix does not subsume rotational transformations. This may limit certain geometric inductive biases present in RoPE, which arise from its rotation- based structure, such as its structured dependence relative position. Extending PaTH with compositions of reflections to approximate rotations, similar in spirit to DeltaProduct [69], is an interesting direction for future work.
7 Conclusion
This work introduces PaTH, new data dependent multiplicative position encoding scheme that prov- ably enhances the expressive power of Transformers. We develop a FtashAttention style blockwise algorithm to enable efficient parallel training. Experiments show that PaTH consistently outperforms RoPE across multiple benchmarks, with particularly strong gains on state tracking tasks and length extrapolation.
10

---

Acknowledgements
This study was supported part by the AI2050 program at Schmidt Sciences (Grant G-25-67980), MIT-IBM Watson Al Lab, and the CSAIL Felicis Research Program. We also thank Zhixuan Lin for helpful discussions.
References
[1] Arora, S. Eyuboglu, A. Timalsina, Johnson, M. Poli, J. Zou, A. Rudra, and Ré. Zoology: Measuring and Improving Recall in Efficient Language Models. CoRR, abs/2312.04922 2023.
[2] S. Arora, S. Eyuboglu, M. Zhang, A. Timalsina, S. Alberti, D. Zinsley, J. Zou, A. Rudra, and C. Ré. Simple linear attention language models balance the recall-throughput tradeoff. CoRR, abs/2402.18668, 2024. doi: (0.48550/ARXIV.24000 18668. URL httph://dool org/
10.
2402. 18668.
arXiv: 2402. 18668.
[3] Y. Bai, X. Lv, J. Zhang. H. Lyu, J. Tang, Z. Huang. Z. Du, X. Liu, A. Zeng. L. Hou, Y. Dong, J. Tang, and J. Li. LongBench: A bilingual, multitask benchmark for long context understanding. In L.-W. Ku, A. Martins, and V. Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 3119-3137, Bangkok, Thailand, Aug. 2024, Association for Computational Linguistics. doi: 10.18653/v1/ 2024.acl-long 172. URL
org/
172/.
[4] S. Bhattamishra, M. Hahn, P. Blunsom, and V. Kanade. Separations in the representational capabilities of transformers and recurrent architectures. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[5] C. H. Bischof and C. V. Loan. The WY representation for products of householder matrices. In SIAM Conference on Purallel Processing for Scientific Computing, 1985. URL https: / //api. semanticscholar
Prrg/CorpusDDi ID: 36094006.
[6] Y. Bisk, R. Zellers, R. LeBras, Gao, and Y. Choi. PIQA: reasoning about physical common- sense in natural language. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 7432-7439. AAAI Press, 2020.
URL https: :tapps://aaa/ //aaai. org/ / jts/ojssss//// ///sidex..p/////eeeeeeeeeeeeeeee php/
[7] B. Chen, X. Li, Y. Liang, J. Long, Z. Shi, and Z. Song. Circuit complexxiy bounds for rope-based transformer architecture, 2024. URL https: : //rxxxaxivvva/////// org/
07602.
[8] S. Chen, S. Wong, L. Chen, and Y. Tian. Extending context window of large language models via positional interpolation, 2023. URL https:///aaxii org/ ab////bb..20.... 15595.
[9] N. M. Cirone, A. Orvieto, B. Walker, C. Salvi, and T. Lyons. Theoretical foundations of deep selective state-space models. In The Thirty-eighth Anmual Conference Neural Information Processing Systems, 2024. URL
[10] P. Clark, I. Cowhey, O. Etzioni, T. Khot, A. Sabharwal, C. Schoenick, and O. Tafjord. Think you have solved question answering? try arc, the ai2 reasoning challenge. ArXiv preprint, abs/1803. /e//1803305557 2018. URL https://arxil:
werg/abs//ie 1803. .5457..
(11) R. Csordás, K. Irie, and J. Schmidhuber. The neural data router: Adaptive control flow in transformers improves systematic generalization. International Conference on Learning Representations, 2022. URL https::/ http:///pweerrreeeeeeeeeooo/t/ea
[12] T. Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. In The Tweifth International Conference on Learning Representations, 2024. URL https:// openreview net:/forumiiddmn22iyyytee
[13] Dao and Gu. Transformers are ssms: Generalized models and efficient algorithms through structured state space duality. arXiv preprint arXiv:2405.21060, 2024.

---

[14] T. Dao, D. Y. Fu, S. Ermon, A. Rudra, and C. Re. Flashattention: Fast and memory-efficien exact attention with IO-awareness. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors. Ad Advances in Neural Information Processing Systems, 2022. URL https::/ net/ forum?id Dorumiid-H4qqPSiimae
[15] T. Dao. D. Haziza, F. Massa, and G. Sizov. Flash-decoding for long-context inference, October 13 2023. URL https: //pytorc/
[16] Devlin, M.-W. Chang, K. Lee, and Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technolo- gies, volume 1 (long and short papers), pages 4171-4186, 2019.
[17] P. Dufter, M. Schmitt, and H. Schütze. Position information in transformers: An overview. Computational Linguistics, 48(():733-763, 2022.
[18] E. Ewer, D. Chae, T. Zeng, J. Kim, and K. Lee. Entp: Encoder-only next token prediction, 2025. URL https:///axiiiii org/ /21s/211.... 01600.
[19] E. Fagnou, Caillon, B. Delattre, and A. Allauzen. Chain and Causal Attention for Efficient Entity Tracking. In Y. Al-Onaizan, M. Bansal, and Y.-N. Chen, editors, Proceedings of the 2024 Conference on Empirical Methods Natural Language Processing, pages 13174-1318 Miami, Florida, USA, Nov. 2024. Association for Computational Linguistics. doi: 10.18653/ 11/2044emmll-mminn 731. URL https: /ataa/aaaannooogooyoooo . org/ 2024. emnlp-main. 731/.
[20] D. Goldstein, E. Alcaide, J. Lu, and E. Cheah. RADLADS: Rapid attention distillation to linear attention decoders at scale. In Second Conference on Language Modeling, 2025. URL
[21] O. Golovneva, T. Wang. J. Weston, and S. Sukhbaatar. Contextual position encoding: Learning to count what's important, 2024. URL pttttts://aarrat
orgooog///ao. Sarrg/bbs/// abs/2405. 18719.
[22] R. Grazzi, Siems, J. K. Franke, A. Zela, F. Hutter, and M. Pontil. Unlocking state-tracking in linear RNNs through negative eigenvalues. In The Thirteenth International Conference on Learning Representations, 2025. URL h/tp:s///pperrviee
[23] C.-P. Hsieh, S. Sun, S. Kriman, S. Acharya, D. Rekesh, F. Jia, and B. Ginsburg, RULER: What's the real context size of your long-context language models? In First Conference on Language http///orrnnnndiiooooooooo/
Modeling, 2024. URL https: //tp::////eeeeeeeeeeeeeee
[24] S. Hu, Y. Tu, X. Han, C. He, G. Cui, X. Long. Z. Zheng, Y. Fang, Y. Huang, W. Zhao, X. Zhang, Z. L. Thai, K. Zhang, C. Wang, Y. Yao, C. Zhao, Zhou, Cai, Z. Zhai, N. Ding, C. Jia, G. Zeng. D. Li, Z. Liu, and M. Sun. Minicpm: Unveiling the potential of small language models with scalable training strategies, 2024. URL httts://axxxxi org./i.oorrr//oooo orgooogg//aoo.oee /a////bbs////// 06395.
[25] Z. Huang, D. Liang, P. Xu, and B. Xiang. Improve transformer models with better relative position embeddings. arXiv preprint MiXix:2009.1355: 2020.
[26] S. Jelassi, D. Brandfonbrener, S. M. Kakade, and E. Malach. Repeat After Me: Transformers are Better than State Space Models at Copying. CoRR, abs/2402.01032, 2024. doi: 10. arXiv:
44550/ARXIV.2402.01033 URL https::///dol wtt//10.484500/rr2..... 48550//855i....//// 2402. 01032. 2402.01032.
[27] T. Joffrain, T. M. Low, E. S. Quintana-Ort,, R. A. van de Geijn, and F. G. V. Zee. Accumulating householder transformations, revisited. ACM Trans. Math. Sofnw, 32:169-179 2006. URL https://api.
www.nti http:://ap..emmmtiiccoooooo
org wwrg/CorpusID-... 15723171.
[28) G. Ke, D. He, and T.-Y. Liu. Rethinking positional encoding in language pre-training. arXiv preprint arXiv:2006. 155955 2020.
[29] N. Kim and S. Schuster. Entity Tracking in Language Models. In A. Rogers, J. Boyd- Graber, and N. Okazaki, editors, Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pages 3835-3855, Toronto, Canada, July 2023. Association for Computational Linguisties. doi: 10. 186538v11202222 a2l long URI. https: / //aaalaaaa aclanthology org 202//2223.o0 aol-long... 213/.
12

---

[30] W. K. Kirchner. Age differences in short-term retention of rapidly changing information. Journal of experimental psychology, 55(4):352, 1958.
[31] T. Kočiský, J. Schwarz, P. Blunsom, C. Dyer, K. M. Hermann, G. Melis, and E. Grefenstette. The NarrativeQA reading comprehension challenge. Transactions of the Association for Computational Linguistics, 6:317-328, 2018. doi: 10.1162/tacl a 00023. URL https:// aclanthology.oo wtt//oo-////// 1023/.
[32] K. Kogkalidis, J.-P. Bernardy, and V. Garg. Algebraic positional encodings. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: // //pperrvvi...et//forrrattaa net/forummid df-feeerxx.....
[33] Y. Kuratov, A. Bulatov, P. Anokhin, I. Rodkin, D. Sorokin, A. Sorokin, and M. Burtsev. BABILong: Testing the limits of LLMs with long context reasoning-in-a-hayttae in-a-haysttakk. In The Tiiht Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024. URL https: https::/opeeerrriiieee http//ppnnvveeeeeee/eeee wwtp:eeeeeetetnieeeeeeeeeeeeoeet wow.oommmdddd2222245555
[34] W. Kwon, Z. Li, S. Zhuang, Sheng, L. Zheng, C. H. Yu, J. E. Gonzalez, H. Zhang, and I. Stoica. Efficient memory management for large language model serving with pagedattention. Proceedings of the 29th Symposium on Operating Systems Principles, 2023. URL https: / //api. www.ssmmmaiiccchlla.... wwwaaar.rr//ooooe wrgg/orrpusD::211677555
[35] Y. Leviathan, M. Kalman, and Y. Matias. Selective attention improves transformer. In The Thirteenth International Conference on Learning Representations, 2025. URL https:// openreview nwt/ d=vOFzmPCäle..
[36] B. Z. Li, Z. C. Guo, and J. Andreas. (how) do language models track state?, 2025. URL https://arxx http:/awww.../aa/aa/////.../..lt abs// 02854.
[37] J. Li, A. Fang, G. Smyrnis, M. Ivgi, M. Jordan, S. Gadre, H. Bansal, E. Guha, S. Keh, K. Arora, Garg, R. Xin, N. Muennighoff, R. Heckel, J. Mereat, M. Chen, S. Gururangan, M. Wortsman, A. Albalak, Y. Bitton, M. Nezhurina, A. Abbas, C.-Y. Hsieh, D. Ghosh, J. Gardner, M. Kilian,
H. Zhang, R. Shao, Pratt, Sanyal, G. Ilharco, G. Daras, K. Marathe, A. Gokaslan, J. Zhang,
K. Chandu, T. Nguyen, I. Vasiljevic, S. Kakade, S. Song, S. Sanghavi, F. Faghri, S. Oh,
L. Zettlemoyer, K. Lo, A. El-Nouby, H. Pouransari, A. Toshev, S. Wang. D. Groeneveld,
L. Soldaini, P. W. Koh, J. Jitsev, T. Kollar, A. G. Dimakis, Y. Carmon, A. Dave, L. Schmidt, and Shankar. Datacomp-In Im: In search of the next generation of training sets for language models, org/a abs/////////// abs/2400 /400 11794.
2025. URL /ttps://arxiss
[38] S. Li, F. Xue, C. Baranwal, Y. Li, and Y. You. Sequence Parallelism: Long Sequence Training from System Perspective. In A. Rogers, J. Boyd-Graber, and N. Okazaki, editors, Proceedings of the 61st Annual Meeting of the Association for Computational Linguisties (Volume Long Papers), Toronto, Canada, July 2023. Association for Computational Linguistics.
[39] Z. Lin, E. Nikishin, X. He, and A. Courville. Forgetting transformer: Softmax attention with forget gate. In The Thirteenth International Conference on Learning Reprexentations, 2025. URL https: htttp:://openreeee http///ppeeeeeeeeeeeeeeeeeeeeeet wwt. wtatt//frmmmidddeee htte//rrrrrdddddggeeggeeee.
[40] Z. Lin, J. Obando-Ceron, X. O. He, and A. Courville. Adaptive computation pruning for the
forgetting transformer, 2025. URL https: http///axvvvvv. wtw.aaiwww.a.aaaaaaaaaeaaeooleee arggabbs/2044. www.//55040699.... 06949.
[41] B. Liu, J. T. Ash, S. Goel, A. Krishnamurthy, and C. Zhang. Exposing attention glitches with flip-flop language modeling. In Thirty-sevnnth Conference on Neural Information Processing Syslems, 2023. URL
[42] B. Liu, J. T. Ash, S. Goel, A. Krishnamurthy, and C. Zhang. Transformers learn shorteuts to automata, 2023. URL
abs /aabs/221.... 10749.
[43] H. Liu, M. Zaharia, and P. Abbeel. Ring Attention with Blockwise Transformers for Near- Infinite Context. ArXiv, abs/23 10.0289, 2023.
[44] X. Liu, H. Yan, S. Zhang, C. An, Qiu, and D. Lin. Scaling laws of rope-based extrapolation, 2024. URL https: / /arxivv org/ abs/2310 2t2pa/299....0...... 05209.
13

---

[45] A. Liutkus, O. Cıfka, S.-L. Wu, U. Simsekli, Y.-H. Yang. and G. Richard. Relative positional encoding for transformers with linear complexity. In International Conference on Machine Learning, pages 7067-7079. PMLR, 2021.
[46] 1. Loshchilov and F. Hutter. Fixing weight decay regularization in adam. In International Conference on Learning Representations (ICLR), 2018. id=rk6ufqLU-
pepperreviev.ee//frrmnt net/forum?
[47] A. Mathiasen, Hvilshøj, J. R. Jørgensen, A. Nasery, and D. Mottin. Faster Orthogonal Parameterizationn with Householder Matrices. In ICML Workshop on Invertible Neural Networks and Normalizing Flows, 2020.
[48] A. Mathiasen, F. Hvilshøj. J. R. Jørgensen. A. Nasery, and D. Mottin. What if Neural Networks had SVDs?, Sept. 2020. URL http://arxiv. wrggabs/2000. http:///araav.or//ab//0000 [es].
13977. arXiv:2009.139
[49] W. Memrill and A. Sabharwal. The expressive power of transformers with chain of thought. arXiv preprini arXiv:2310.07923, 2023.
[50] W. Merrill and A. Sabharwal. A logic for expressing log-precision transformers, 2023. URL attps://arxinn wwt./or/////a///////
[51] W. Merrill, J. Petty, and A. Sabharwal. The Illusion of State in State-Space Models, Apr. 2024. URL http:///axiiii wwtp/rg/g/bb....a.e/////// 28819944008819 arXiv:2404.08819 [cs].
[52] M. Milakov and N. Gimelshein. Online normalizer calculation for softmax, 2018, URL https://arxiie .twpsiiioor///oooooo org/ abs/1805.028677
[53] D. Paperno, G. Kruszewski, Lazaridou, Q. Q. Pham, R. Bernardi, Pezzelle, M. Baroni, G. Boleda, and R. Fernández. The LAMBADA dataset: Word prediction requiring broad dis- course context, June 2016. URL http::/ttx:/ii orgg/bs///00/ 06033.. [cs].
06031. arXiv:1606.0660
[54] G. Penedo, H. Kydlfček, L. B. Allal, A. Lozhkov, M. Mitchell, C. Raffel, L. V. Werra, and T. Wolf. The Fine Datasets: Decanting the Web for the Finest Text Data at Scale. Nov. 2024. URL https: http///pppeeeiiieeeeeeeeee
[55] B. Peng, J. Quesnelle, H. Fan, and E. Shippole. Yarn: Efficient context window extension of large language models, 2023. URL
wtt//os//////eeeeeee ab3//3/9/////../////// 00071.
[56] B. Peng, Zhang. D. Goldstein, E. Alcaide, H. Hou, J. Lu, W. Merrill, G. Song, Tan, S. Utpala, N. Wilce, J. S. Wind, T. Wu, D. Wuttke, and C. Zhou-Zheng. Rwky-7 "goose" with expressive dynamic state evolution, 2025. URL / //arxiv.//// orgo argg/bbs/5503. 14456.
[57] N. Prakash, T. R. Shaham, T. Haklay, Y. Belinkov, and D. Bau. Fine-Tuning Enhances Existing Mechanisms: A Case Study Entity Tracking. Oct. 2023. URL htt.httts://opnreeeeee forum?)d-=SsKcAADD22.
net/
[58] O. Press, N. A. Smith, and M. Lewis. Train short, test long: Attention with linear biases enables input length extrapolation, 2022. URL pattts://arxiar wrg.iiiiiorr/eeeooe httg//bb/21088.. 12409.
[59] Z. Qin, W. Sun, K. Lu, H. Deng, D. Li, X. Han, Y. Dai, L. Kong, and Y. Zhong. Linearized relative positional encoding. Transactions on Machine Learning Research, 2023. ISSN 2835- 8856. URL https: /estps:/oppeet http:////peeeeeeeeeeee net/
[60] Qwen, A. Yang. B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Li, D. Liu, F. Huang, H. Wei, H. Lin, J. Yang, J. Tu, J. Zhang, J. Yang. J. Yang, Zhou, J. Lin, K. Dang, K. Lu, K. Bao, K. Yang, I.. Yu, M. Li, M. Xue, P. Zhang, Q. Zhu, R. Men, R. Lin, T. Li, T. Tang, T. Xia, X. Ren, X. Ren, Y. Fan, Y. Su, Y. Zhang, Y. Wan, Y. Liu, 2. Cui, Z. Zhang, and Z. Qiu. Qwen2.5 technical report, 2025. URL https://: htapps:///aaivv.//teeeeess www.iiioor//ab//22/
[61] M. Rabe and C. Staats, Self-attention Does Not Need $2)S Memory, Oct. 2022, URL attp://arxiv org arggabbs2112.. 05682. arXiv:21 [cs].
14

---

[62] J. W. Rae. A. Potapenko, S. M. Jayakumar, C. Hillier, and T. P. Lillicrap. Compressive transformers for long-range sequence modelling. In International Conference on Learning Representations, 2020. URI. https:://///t fttt:p:///peereviiee "arrerrrvee..net/oruummmmm ttttfforumidd-SyyKe
[63] C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou, W. Li, and P. J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21(140): 67, 2020.
[64] K. Sakaguchi, R. L. Bras, C. Bhagavatulla and Y. Choi. Winogrande: An adversarial winograd schema challenge at scale. In The Thirty-Forrhh AAAI Conference on Artificial Intelligence, AAAI 2020, The Shirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, FAAI 2020, New York, NY, USA, February 7-12, 2020, pages 8732-8740. AAAI Press, 2020. URL. http::://///// /awa///aaaaa//////a///aaa/aaaaaa org/ jtt////ss//////// httss//idx..pppeee php/ AAAT httaa/artcceeeeeeeeeeeeee
[65] I. Schlag, K. Irie, and Schmidhuber. Linear transformers secretly fast weight programmers, 2021. URL https: http://axxxv....gbbbbeaae /bgga// 11174.
[66] I. Schlag, K. Irie, and J. Schmidhuber. Linear Transformers Are Secretly Fast Weight Program- mers. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021. Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 9355 9366. PMLR, 2021.
[67] R. Schreiber and C. Van Loan, A storage-efficient wy representation for products of householder transformations. SIAM Journal on Scientific and Statistical Computing, 10(1):53-57, 1989.
[68] J. Shah, G. Bikshandi, Y. Zhang, V. Thakkar, P. Ramani, and T. Dao. FlashAttention- 3: Fast and Accurate Attention with Asynchrony and Low-precision. Nov, 2024. URL htttps://operrett wtw.:/arwrreeeeeeeeeeeeoreeeeeoa
[69] J. Siems, T. Carstensen, A. Zela, F. Hutter, M. Pontil, and R. Grazzi. Deltaproduct: Increasing the expressivity of deltanet through products householders, 2025. URL //attps://rxiv. org brggabs//000 /ta.b//2502.029999
[70] Z. Song, P. Sun, H. Yuan, and Q Gu. Causal attention with lookahead keys, 2025. URL https://arxiv /twriv..rr/////////////o/ org/ abs/ 2020/250.07701.. 07301.
[71] B. F. Spector, S. Arora, A. Singhal, A. Parthasarathy, D. Y. Fu, and C. Re. Thunderkittens: Simple, fast, and Sitextit Adorable)$ kernels. In The Thirteenth International Conference on Learning Representations, 2025. URL https::/openreet
net/fformmidd-00 O
[72] J. Su. Y. Lu. S. Pan, A. Murtadha, B. Wen, and Y. Liu. Roformer: Enhanced transformer with rotary position embedding, 2023. URL https: /ttp:/::///xvv//aeaaeee abs//104 09864.
[73] S. Tan, S. Yang, A. Courville, R. Panda, and Y. Shen. Scaling stick-breaking attention: An efficient implementation and in-depth study. In The Thirteenth International Conference on Learning Representations, 2025. URL https: / opw.reveeeeeeeeee//e/eeee. wppeereveee.ee//orrrrrr peet/foorumiddrrJ300000
[74] A. Terzié, M. Hersche, G. Camposampiero, T. Hofmann, A. Sebastian, and A. Rahimi. On the expressiveness and length generalization of selective state-space models on regular languages. In Proceedings of the AAAI Conference Artificial Intelligence, 2025.
[75] P. Tillet, H.-T. Kung, and D. D. Cox. Triton: intermediate language and compiler for tiled neural network computations. In T. Mattson, A. Muzahid, and A. Solar-Lezama, editors, P Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, MAPL@ PL.DI 2019, Phoenix, AZ, USA, June 22, 2019, pages 10-19. ACM, 2019. doi: 10.1 10.1145/3115588.3229977
[76] A. E. Tomás Dominguez and E. S. Quintana Orti. Fast Blocking of Householder Reflectors on Graphics Processors. In 2018 26th Euromicro International Conference on Parallel, Distributed and Network- Processing (PDP), pages 385-393, Mar. 2018 doi: 10.1100/PDP201..20 00068. URL https:/ http::///eeeeeporeeee/ ieee. org/ //ccummnt///744999 ISSN: 2377-5750.
15

---

[77] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and
I. Polosukhin. Attention is all you need, 2023. URL https: wrgg/bs///// 03762.
[78] Yang. Deltanet explained (part ii), 2024, URL /lgg/2224/eeltantt
io/
Accessed: 2025-03-26.
[79] S. Yang and Y. Zhang. FLA: A Triton-Based Library for Hardware-Efficien Implementations of Linear Attention Mechanism, Jan. 2024. URL /ttt::///ghhutt com/ htt/:usstssoo coonglisn flash-linear- attentionn original-date: 2023- 12-20100::001182.
[80] S. Yang, B. Wang, Shen, R. Panda, and Y. Kim. Gated Linear Attention Transformers with Hardware-Efffcient Training, CoRR, abs/2312.066333 2023, doi: 00448500ARXIVV2312.06666 URL https://dol: org/10 10. 48550/ arxiv. 06635. arXiv: 2312.06635.
[81] S. Yang, B. Wang, Y. Zhang, Shen, and Y. Kim. Parallelizing linear transformers with the delta rule over sequence length. In Proceedings of NeurIPS, 2024.
[82] S. Yang, J. Kautz, and A. Hatamizadeh. Gated delta networks: Improving mamba2 with delta rule. In The Thirteenth International Conference on Learning Representations, 2025. URL https: http:::///ppeeevieee
[83] R. Zellers, A. Holtzman, Y. Bisk, A. Farhadi, and Y. Choi. HellaSwag: Can machine really finish your sentence? In A. Korhonen, D. Traum, and L. Mårquez, editors, Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4791-4800, Florence, Italy, 2019. Association for Computational Linguistics. doi: 10. 12.18//111111914422 URL https: httpa/////caaaahhlooggee www.ollooyy.og//ggg11g 1472.
[84] Y. Zhang, W. Du, D. Jin, J. Fu, and Z. Jin. Finite state automata inside transformers with chain-of-thought: A mechanistic study state tracking, 2025. URL abs/2502. 20t.2299....9..
[85] C. Zheng, Y. Gao, Shi, M. Huang, Li, Xiong, X. Ren, M. Ng. Jiang, Z. Li, and Y. Li. DAPE: Data-adaptive positional encoding for length extrapolation. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: / //openreview wett:formmidddruUUUUS
[86] C. Zheng, Y. Gao, H. Shi, Xiong, J.
Sun, J. Li, M. Huang, X. Ren, M. Ng. X. Jiang, Z. Li, and Y. Li. Dape v2: Process attention score as feature map for length extrapolation, 2024. URL https:/ http:://aaaivieee www.i.owg/aaaaaa.......oweeeeaea //tp///110000220
[87] Zhou, Wang, N. Ranjan, Z. Cheng, L. Tang. G. He, Z. Liu, and E. P. Xing. Megamath: Pushing the limits of open math corpora, 2025. URL htttt://aaxxii wwrzxiv.org/abii org/abs/ 2504. 02807.
[88] Y. Zhou, U. Alon, X. Chen, X. Wang, R. Agarwal, and D. Zhou. Transformers can achieve length gencralization but not robustly, 2024. URL https: :tttps://arxiv. www./oor/////aaaaeee 09371.
16

---

A Representation Power of Transformers with PaTH Attention
We state two theorem which illustrate the representation power of transformers equipped with PaTH attention.
The first theorem shows that PaTH attention layer solve the problem of tracking iterative swaps on 5 elements, which is an NC cCmmpeplet under AC reductions. This theorem and its proof is an adaptation of Theorem of Peng et al. [56].
Theorem 2.1. one-layer PaTH transformer with two attention heads and log n precision can solve NC² -complete problem under -reduucct.s
Proof. As in Lemma of Peng et al. [56], consider the task of deciding whether iterative swappings of 5 elements encodes the identity permutation. This task consists of input sequence CgCI ... Cp of length n +
[a1 ++ bi] [a2 +> b2] Jan ++ bn]
where co # is the start token and indicates that position on is swapped with position 6, at time n. (Hence there are such possible swap tokens of the form [r + y) for all pairwise 2, {l....,5) 5] such that z * y.) Given this sequence, we show that there is a one-layer PaTH transformer with two attention heads that outputs a 1 if the sequence encodes the identity permutation, and -1 otherwise. As noted by previous works [51, 56], this suffices since there is an AC -cduuuuut from well-known NC² -comopeee problem (i.e., iterated multiplication of S;)) to this task.
[a1 ++ bi].....
[a,, <> bn] are "tokens" which
We first embed the # and all 20 [x + y] tokens to distinct one-hot vectors. Given a token u E E and its associated one-hot vector u, we choose the aey/queryyvalue/PPTHH projection matrices (i.e.. W W W.. W.. R matrices for the first attention head such that
u = k(u] = (u # (el + 202 + 3e3 + 4e + 5e, - -6),
W u [u] ne(e + 2e + 3e3 4e4 + 5es + 54.5es),
W 11 w [u] (e, e,)/ for [ar <> v). and = #
W u v(u) 1 I( #}e
2.
(Hence, the query vectors and 3 are input-independent)) In this case, as in Lemma of [56] the one-step PaTH transformation is a true Householder transformation with
H [ = I 2w [w/u]w[u] E g
and effectively swaps with y. Now suppose the initial list is [1, 4, 5,5). and let x(i) be the i-th element of the final permuted list after the n swaps. We then have
n
((=
5 ie)(i)
(k[co]
Il H.)
e6
and the attention logit from 0 is given by
5
so
k/co]
I H.q
Σ
im
54.5
s=1
By the rearrangement inequality, we further have
5 M 2
Σ
iT(
55,
with equality holding if and only i- x (1) for all Therefore 8o > 0.5m if the final list is the same the initial list (i.e., identity permutation). and so -0.5n otherwise. Because k/uj 0 for all u + #. we further have that the attention logits 8j for all / > 0 is 0. The attention weight for the first which is greater than n+1 if > 0 (i.e., permutation is position is then given by ag exp(so)-n
exp(se)
17

---

identity) and less than 2+1 otherwise. Since the value vector is e₁ for and 0 otherwise, the output of this attention head is given by
exp(s0) exp(s0) +
aivia]
e1.
The second attention head is data-independent and uses We W W. 0, and the same value matrix W. above. This results in the output of this second attention head always being C1 regardless of the input. Concatenating the output from these two heads gives the vector
exp(sa) exp(s0) +
1
0. 0,0,0,0,0,
72 ++11 0,0.0.0,0
ie., 12 dimension vector with the first dimension as exp(so)-n and the 7th dimension as x+1' We can now have an output projection layer with matrix W. that subtracts the 7th dimension from the 1st dimension (i.e., 0, 0, 0, 0, 0, 0, O, 0] in the first row). The first dimension of this output vector will be positive if the permutation is identity, and negative otherwise. We can then use the FFN layer with sign(-) nonlinearty (or steep tanh function) to clamp this output to {-1,+1}.
exp(so)
We do not explicitly need the log n precision assumption here but the construction here can be represented in log precision while preserving the same functionality. We include this assumption to ensure that we are using same or weaker precision assumption with previous works on the circuit complexity of transformers (Merrill and Sabharwal [50]. Chen et [7] and refs. therein). We can make the proof simpler in the above if we incorporate a O (log n) assumption since in this case the output of softmax is when the final list is the same as the original list and is otherwise (i.e., there is no need for the second attention head).
Theorem A.I. For any there is a two-layer PaTH transformer with n) precision solve the flip-flpp language modeling (FFLM) task with accuracy greater than 1/n 100 for all inputs up to length n.
Proof. Recall that in FFLM, there are five types of input w, i, r, O, 1. We will now present construction the two-layer transformer with PaTH attention.
The token embeddings are given by
emb(w) e +
emb(r) e + e6
emb(1) C3 + C6
emb(O) e4 + e6
emb(1) e5 +e6
where e; is the one-hot i-th basis vector.
The first attention layer will implement a one-hot attention from the bit tokens and to their corresponding instruction tokens. To achieve this, we will have the matrices W W W such that:
qo wa W,
Wgh = (h1 + h2 + ha)e1,
W W,h nhoel,
W h = (h1 + h12 + hajei + (h4 + h5)e2,
W. h hi07 + hscs hycs,
B 1.
Then the transition matrix is given by
e e if input is (w, r, i)
e if input is (0, 1).
18

---

ie.. the transition matrix projects the first dimension to 0 for the instruction tokens {w. r, i) and projects the second dimension to 0 the bit tokens f0, 1). Similarly, the key vector k; ej if the i-th token is an instruction token, and 0 otherwise. Therefore when the i-th token is 0 or
i
kj
II H.q. +0 6=/+1
if and only j i-1 and in this it equals n. Because we considering (log n) precision transformer, the attention score after softmax becomes 1-hot for every bit token. After this attention layer, the 7-th 9-th dimension of the bit tokens now encode the type instruction the previous token.
The first FFN layer will map the to dimensions of O and tokens to be one-hot embedding for each value and corresponding instruction type,
FhN 0, & {10, 11, 12), FFN(b)10 1 = 1, h7 = 1}:
FFN 1(hs 1, = 1}.
FFN = 1, otherwise.
With 1(-} being the indicator function. Specifically, the 10-th dimension will be for every following and the 11-th dimension will be 1 for every following w.
The second attention layer will operate on the 10-th and 11-th dimensions of the input embedding and implement the following:
Wgh = (h10 + h11)e1
W,h n/ge1
W wh = (h1o + hnjer + h1202
W hge13 hge14
(hh) = 1[sh + hg > 0}
Here assume that logistic function for it to be effectively a step function under the precision considered). This shows that for every token that is not follows w, the transition matrix is a matrix that projects the first dimension to O. Then for any 2 2.
step function for (or alternatively,
steep-enough
that follows w, the transition matrix is identity; for 0 or 1 that
kJ II H.q. #0 s=st1
if and only if j is the largest token that is exist because F,,M, the first token is always w. In this case, this term equals n. Using the same argument the first layer, the attention becomes one-hot and the output of attention encode the value of last 0 or token following w. By the definition of flip-flop, this the current state.
that follows with j S i. This j guaranteed to
The second FFN layer will operate the 13-th and 14-th dimensions of the input,
FFN(h); = 0, g (15, 16).
FFN 15 1 1, 1);
FFN 1(h2 = 1, 1).
Specifically, the 15-th and 16-th dimension of the output will encode the state value for each token. After this layer, dimensions 1, 3, 4, 5, 15, and 16 of the embedding becomes one-hot, each corresponding to a different output distribution in FFLM.
Finally, the LM head will map dimensions 3, 4, 15, and 16 to their corresponding next-token probability before softmax. Concretely.
WLMh
(Tee + Ths + ha)
+(Tei + +Te + Te3) + hs)
tnegh1s + neghi6.
Here As log an appropriate number such that softmax over Tea Tes and Tej + Tez + Teg yields uniform distribution with error smaller than 1/n 101
D
19

---

Task
Example
Evaluation Focus
Task 1: Single Supporting Fact
Mary
the bathroom. John moved to hallway.
Identify single explicit fact from context.
Mary travelled to the office. Q: Where is Mary? A: office John is in the playground. John picked up the football.
Task 2: Two Sup- porting Facts
Combine two clues to infer object's 's location.
Bob went to the kitchen.
Q: Where the football? A: playground
Task 3: Three Supporting Facts
John picked up the apple. John went to the office.
Track object movement and temporal order.
John went to the kitchen.
John dropped the apple. Q: Where was the apple before the kitchen? A: office
Task 4: Two Ar- gument Relations
Office is north of bedroom. Bedroom is north of bathroom.
Reason over spatial rela- tionships.
Kitchen west garden. Q1: What is north bedroom? A: office
Q2: What is bedroom north of? A: bathroom
Task 5: Three Ar- gumeet Relations
Mary gave the cake to Fred.
Transitive reasoning over possession chains.
Fred gave the cake to Bill.
Jeff given the milk by Bill.
Q1: Who gave the cake Fred? A: Mary
Q2: Who did Fred give the cake to? A: Bill
Table 6: Descriptions and examples of the first five bAbl tasks. Each task highlights specific reasoning skill required for successful question answering.
B Experimental Setup & Additional Results
QA1
50
16
08
160
Sequarce Langth
Lengt
FUTH
RAPE
Seguerce Langth
Secuence Length
Figure 5: BABILong performance breakdowns. QAI: Single supporting fact. QA2: Two supporting facts. QA3: Three supporting facts. QA4: Two arg relations. QAS: Three arg relations.
Hyperparameter settings. All models are trained with AdamW [46], using a cosine learning rate schedule with BB-token warmup. The peak learning rate is le-3, with both initial and final rates set to 3e-5. We apply a weight decay of 0.01 and gradient clipping of 1.0. The batch size is 2M tokens. Parameters are initialized with a standard deviation of 0.02. Each 760M model is trained on H1 GPUs for 2-3 days. For synthetic tasks, we use A100 GPUs, completing training within several hours.
BABILong Figure presents the performance breakdown across sub-tasks and sequence lengths.
Task descriptions provided in Table 6.
20

---

LongBench-EE Detailed results are presented in Table 7.
Category
Dataset
4k
8k
Sk-16k
FoX FoX-PaTH
PaTH
RoPE
FoX
FoX-PaTH
PalH
RoPE
FoX
PoX-PaTH
PaTH
RoPE
2uikinga
21.0
23.7
28.7
23.9
15.3
22.5
20.8
0.9
9.4
8.4
7.3
0.1
hotpotqa
20.3
16.2
19.0
25.2
9.3
16.1
22.8
0.8
5.6
7.7
8.8
0.4
QA
moltifieldqs_ee
39.1
39.6
38.6
18.0
24.9
31.4
27.2
19.5
19.2
qaeper
22.4
24.6
25.9
15.1
14.9
19.8
16.8
1,8
7.0
10.1
10.6
1.9
Summarization
malti_news
9.1
6.9
12.1
10.2
7.3
9.8
9.6
3.1
6.1
8.3
8,3
1.7
gov gov_report
14.4
10.2
22.3
12.4
14.5
13.6
17.9
4.9
5.9
11.9
11.6
2.5
trec
35.0
36.7
40.0
23.3
27.5
26.3
35.0
1.2
20.6
26.3
20.0
0.0
Fow-shot
triviage
33.2
28.9
36.0
21.8
18.2
27.6
32,0
2.8
13.7
31.6
18.4
0.4
sansum
21.4
27.1
26.8
19.3
16.9
27.6
23.6
3.2
9.1
15.7
15.6
0.7
21.4
22.3
22.1
23.3
18.6
18.9
19,0
Code
repobench-p
21.8
22.7
27.3
14.6
18.4
22.5
22.7
9.2
17.5
19.3
19.2
7.6
Average
23.4
23.5
27.2
18.7
16.9
21.9
22.5
3.7
11.7
16.1
14.4
2.0
Table 7: Performance comparison grouped by task category. Each bolded value indicates the best model score for the respective dataset and length bucket.
21

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See the last sentence of the introduction section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We have a limitation section in 86
22

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes].
Justification:
We have proofs in $A.1, 2.1.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Yes we described the hyperparameter setting in $B
Guidelines:
The answer NA means that the paper does not include experiments.
23

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibilityy which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes].
Justification: We have open-sourced the Triton kernel at https://githu/ com/fle org/ Flash-linee attention, and and our experiments can be reproduced using our main- tained training framework https: //gith/t.tttttt//// com cww/flalorg/flllaae/eaaao
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/ Bttiiii/guudde///oeeeeueee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g.. for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nips.. cc/ppbbic/guideeeeec
cittiisssonPp asionnoiccy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
24

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: See ŞB.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification:
Many pretraining experiments are expensive for academic setting.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See $B
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
25

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttp:////neu.p...eeeee ctt.ipp...p..eeocooooooooe http/pulic/Ehhisauiiieieoc
Answer:
[Yes].
Justification: Yes, have adhered to the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification:
No societal impact that aware of.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper poses such risks.
26

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [No]
Justification: Cited but did not discuss license and terms of use
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No].
Justification:
We do not have new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification: N/A
27

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]-
Justification: N/A
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA].
Justification: N/A
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https httpa///eeeepeeee/oooeeeeeeeeeee wttp:///eeeeeeeee/////////////// for what should or should not be described.
28


Reviews:
[{"review_id": "2g8SdhnmEQ", "reviewer": "Reviewer_UFkx", "summary": "The paper presents a novel position encoding method for transformers that uses data-dependent, accumulated Householder transformations to overcome the expressivity limitations of existing methods like RoPE. Good performance is demonstrated on synthetic benchmarks and real-world language tasks. The method can be efficiently trained at scale using a custom FlashAttention-style algorithm. Ideas on representative power are leveraged from the RNN literature (RWKV-7 and related).", "questions": "- any insights how your method changes attention patterns?\n- can you give more clarity/evidence why the data-dependency is a benefit, compared to traditional pos embeddings which are added to the data  (values) also?\n- (optional) as you inherit many ideas from RWKV-7: would it make sense to ask if similar behaviors (lost in the middle) are present in your transformer compared to RNNs, empirically?\n- any idea if the method could be added to existing LLMs with slight post-training, or needs to be there from scratch? (one can always dream)\n- detail: can you clarify if BoD tokens or meta-tokens were used (related to attention sinks)", "limitations": "- details: clarify which mistral tokenizer", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- I'm impressed by the overall integration of conceptual results with real-world impact, showing benefits on relevant benchmarks in language modeling and long-context tasks at scale, while also showing clock-time speed gains. \n- Elegant idea with the identity plus rank-1 structures\n- Convincing mix of evaluations\n\nWeaknesses\n- (minor) A bit unclear on the practical implications of NC^1 vs. TC^0 (though I do appreciate the synthetic task and proofs)\n- (minor) Nope is not included as another baseline? (Seems to re-gain popularity these days, alone, and also with llama-4 / gemma-style alternating local/global attention, but that's probably orthogonal?)", "was_revised": true, "final_justification": "I'm fine with the outcome of the rebuttal, and remain on the accept side (also given the other positive assessments by reviewers)", "rebuttal": ""}, {"review_id": "vcRjtD8KYN", "reviewer": "Reviewer_V5VP", "summary": "PaTH attention proposes a novel way to encode the positional difference between two tokens in the sequence in a data-dependent manner, not like RoPE (data-independent). This allows us to solve the problems that are not possible to be solved or very hard in RoPE-based attention networks, such as flip-flop language models.", "questions": "- Can you release the code during the rebuttal period? I wanna see actual implementation, and how it is complicated as the paper claimed in the limitation section.", "limitations": "I think the limitation section makes sense and is explicit. However, I want to see more fundamental methodology level limitation, rather than simply claiming common limitations of academic research (limited computing resources and time, limited engineering powers). For example, I want to see how this method is compatible with Flash Attention 3 style optimization (async matmuls, tensor memory accessors, specialized warps, and more)", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "# Strength\n- Their proposed PaTH attention is data-dependent, solves problems of existing softmax attention with RoPE.\n- They also showed a hardware-efficient kernel for inference and training the PaTH attention, which is a very impressive part.\n\n# Weakness\n- This method is not directly compatible with an ordinary RoPE-based attention model, so we cannot apply PaTH attention in a plug-and-play manner. I think at least we should try to transfer training (like this: https://arxiv.org/html/2310.01777v2) from RoPE to PaTH on already released models such as Qwen3. I believe swapping existing softmax attention to PaTH and training with knowledge distillation might make it possible to run PaTH on the existing state-of-the-art models. This would be cheaper to train, and make your method way more impactful. I strongly suggest doing this, even after this submission or paper decisions.\n- Their methodology section is a little bit hard to follow, because every explanation is in text and equations. I think it would be great if we had some figures about methodology and algorithm, like previous papers (FA: https://arxiv.org/abs/2205.14135, Figure 1 Center, LA: https://arxiv.org/pdf/2401.04658, Figure 2).\n- The training curve is missing. I believe the pretraining loss curve is essential information for evaluating whether the training is complete and the proposed method is fully converged compared to the baseline (softmax attention). It might be too small a corpus to train the softmax attention-based Transformer with 50B tokens. So, I think the loss curve might be helpful to convince readers that this method is training very well, compared to existing baselines.\n- Lacks of open implementation. The authors did not submit their code.", "was_revised": true, "final_justification": "All my concerns are resolved, and I believe this paper is strong.", "rebuttal": ""}, {"review_id": "ArRLct96bQ", "reviewer": "Reviewer_8tf9", "summary": "This paper introduces a new method called PATH, which is a flexible data-dependent position encoding method that employs a Householder-like transformation. They provide  theoretical analyses to understand its method.  The paper has also achieved a hardware-efficient implementation of this method. Through multiple experiments, the effectiveness of this method has been demonstrated.", "questions": "1. Comparative Experiment with NoPE ( The impact of positional encoding on length generalization in transformers) \n\n    In the NoPE paper, the authors demonstrated that even without positional encoding, transformers can still perceive position information. In this work, the authors have introduced a data-dependent position encoding method by incorporating a function related to the input. Given that neural networks are capable of simulating such functions, it would be valuable to include a comparative experiment with NoPE to highlight the effectiveness of this design. This comparison would provide clearer insights into the benefits of the proposed data-dependent position encoding.\n\n2. Discrepancy and Concerns in the Flip-flop Experiment\n\n   In the Flip-flop experiment, it has been theoretically proven that two layers can solve the task. However, the actual implementation only utilizes one layer. Could the authors elaborate on the differences between the theoretical and practical outcomes? Additionally, there are some concerns regarding the experimental setup. Since the experiment only employs one layer and the PATH also includes the input function, especially with a limited vocabulary of only 5, it seems that the input function might play a more significant role. This could potentially skew the results and make the comparison unfair. It would be more convincing if the authors could increase the number of layers and redo the experiment to provide a more comprehensive evaluation.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths：\n\n1. The authors introduce a novel data-dependent position encoding method and provide a hardware-efficient implementation. This represents an innovation in the field.\n2. The authors offer theoretical proof that the newly designed method can effectively address the state tracking issue. This has enlightening implications for enhancing the capabilities of existing models.\n3. Through multiple experiments, the authors have demonstrated the effectiveness of the proposed method.\n\nWeaknesses:\n\nThe actual implementation of the algorithm is not very clear. In line 69, the actual formula is given, and then it involves using the UT form (line 121) and hardware-efficient implementation to accumulate P. Since the method is data-dependent and involves a function related to the input, it would be beneficial if the authors could provide a more detailed algorithm flow. Specifically, how is the function integrated into U or P, and what is the actual workflow?", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "uaKZjEX4VY", "reviewer": "Reviewer_6WvM", "summary": "The paper investigates a substitute for the widely-used RoPE positional encoding in language models. Motivated by recent advances in linear RNNs and attention mechanisms, it proposes a multiplicative positional encoding scheme applied between each pair of tokens. It uses the data-dependent, Householder-like matrix with an identity-plus-rank-one structure, where the rank-one components are learnable. Leveraging this structured form, the paper further introduces and implements efficient training kernels that compute the pairwise multiplicative positional encodings efficiently. Experiments are conducted on a 1B-parameter model trained with 50B tokens. Results show that the proposed learnable positional encoding~(PE) outperforms both the classical RoPE and a recently introduced learnable multiplicative PE across synthetic tasks, common-sense reasoning, and long-context benchmarks. The paper also evaluates and compares their performance in length extrapolation scenarios.", "questions": "1. I suggest shortening Chapter 3 and including more experimental results on efficiency.\n\n2. I recommend expanding Chapter 2 and providing more exploration on the design of the H matrix.\n\n3. In Table 2, many tasks include both acc and acc_norm as metrics. However, the paper sometimes reports acc, and other times acc_norm. For example, both ARC-e and ARC-c include these two metrics, but the paper reports acc for ARC-e and acc_norm for ARC-c. This inconsistency appears confusing to me.\n\n4. The current design appears quite similar to some recent approaches in linear RNNs or linear attention mechanisms. As noted around lines 70–80, the main difference lies in the use of the softmax function. It would be helpful if the paper could further explore how this softmax non-linearity affects performance, when compared to its linear counterparts.\n\n5. For additional questions, please refer to the weakness section.", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. The paper addresses the important problem of improving positional encoding in transformer models. Instead of using the fixed RoPE encoding, it introduces a novel learnable multiplicative positional encoding scheme that operates between each token pair.\n\n2. To ensure both expressiveness and computational efficiency, the method employs a Householder-like matrix with an identity-plus-rank-one structure, along with an efficient training pipeline supported by custom Triton kernels.\n\n3. The experiments span a broad range of tasks, demonstrating the method’s effectiveness across classical language modeling benchmarks, long-context tasks, retrieval scenarios, and length extrapolation evaluations.\n\n4. The paper is easy to follow.\n\nWeaknesses\n1. The paper lacks sufficient exploration of alternative designs for the matrix H. Although it follows ideas from recent developments in linear RNNs, the presence of the softmax operation in attention could lead to significantly different behavior. Different choices of H could yield not only different performance but also different computational efficiencies. Moreover, the paper does not explain why Householder matrices are particularly suitable or theoretically motivated in this context.\n\n2. The experimental study on efficiency is insufficient. Although the paper takes three pages for its efficient training and inference approach, the empirical evidence is limited to a single figure. This fails to convincingly demonstrate its competitiveness compared to Attention. Assuming Figure 1 represents training efficiency, it would be helpful to include latency results across different model dimensions as well. Additionally, inference-time performance is not reported. Since Eq. (8) suggests extra computations are required for updating the key vectors, reporting decoding latency would help clarify the inference-time cost.\n\n3. The model architecture details are unclear. For example, Fox introduces modifications such as additional normalization layers beyond the standard transformer design. When combining Fox with the proposed PaTH method, the paper does not clarify which architectural components are used in the experiments. This raises questions about the fairness of comparisons to standard attention-based models.", "was_revised": true, "final_justification": "I think the main problem of this paper is their efficient implementation. I thought it was due to some clarity problems that there are not many efficiency results in the paper. However, based on the discussion, it seems that this is not the case.\n\nWhile efficiency has been a main part of the method and the contribution, the training speed of the single-head PaTH is obviously slower than the parallel attention, and decoding has not been implemented yet, which is extremely important, given that the main bottleneck is caused by the attention.\n\nTherefore, I tend to maintain my score.", "rebuttal": ""}]

Author rebuttal:

Meta-review: The paper introduces a variant of attention, PaTH, which uses a cumulative Householder transformations along with a new data-dependent position encoding scheme. Author provides theoretical expressivity results as well as efficient implementation in FlashAttention-style kernel. Empirical studies show gains on synthetic reasoning, some LM benchmarks, and long-context generalization. All the reviewers were mostly positive about the submission, yet raised important concerns on clarity and details of the algorithm, missing NoPE baseline comparisons, and practical applicability (e.g. whether PaTH could retrofit existing pretrained models). We thank the authors and reviewers for engaging during the rebuttal period to improve the paper. The authors provided a PyTorch reference implementation, clarified the flip-flop setup, and importantly demonstrated knowledge distillation from RoPE to PaTH on Qwen models, showing PaTH largely recovers or improves performance. Based on this one reviewer raised their score, and the others remained positive. While the work would benefit from broader baselines and larger-scale validation with open-sourced code, the submission does provide the community with an attention variant with increased theoretical expressivity and strong experimental results.
Decision: Accept (poster)