Analytic-Walk Rotary Positional Encodings for Graphs

Jiaqing Xie; Yuxin Wang; Xipeng Qiu

cs.LGSep 26, 2026

Analytic-Walk Rotary Positional Encodings for Graphs

Authors: Jiaqing Xie, Yuxin Wang, Xipeng Qiu

Organizations: Shanghai Innovation Institute · Fudan University

Abstract

Rotary position encodings make attention sensitive to relative position, but extending them to graphs requires choosing how graph structure enters the rotation. Previous works assign each node a rotation from spectral coordinates, so the rotary factor between two nodes depends only on their endpoints and cannot distinguish the routes connecting them. We introduce Analytic-Walk Rotary Positional Encodings (AW-RoPE), which place the rotations on edges and sum the transported features over all walks, so contributions along different routes can reinforce or cancel. An exact variant evaluates the complete sum by a differentiable linear solve, and a sparse variant truncates it at a finite depth. We prove forward and parameter-derivative truncation bounds at fixed inputs and parameters. Both variants act on projected queries and keys, and the sparse recurrence also augments message-passing networks. Across five synthetic tasks both variants reduce nRMSE by $15$ -- $58\%$ relative to the strongest baseline, and on real superpixel, peptide and OGB benchmarks the sparse recurrence attains the best mean on every dataset with Performer kernels and on twelve of thirteen datasets with GIN. Analysis shows that AW-RoPE can distinguish routes whose only cue is how two endpoints are connected, while node-wise rotary encodings cannot.

Figures & tables

Panel of Figure 1 — Figure 1: Node-phase cancellation and controlled edge-phase changes. Edge labels are phases in radians ( $\omega=1$ ). (a) With node-wise rotations, every route between the same endpoints accumulates the same phase, so the route gap $\Delta=\theta_{2}-\theta_{1}$ is zero for any node phases. (b) The first AW example uses exactly the same phases. The next two add $\pi/4$ or $\pi/2$ to each forward lower edge. Reverse phases negate. The powers are normalized AW responses with prescribed phases, without fitting the scorer.

Panel of Figure 2 — Figure 2: AW-RoPE implementation. (1) A shared scorer maps node features $\mathbf{H}$ to edge displacements $a_{uv}$ , with $\omega_{\ell}$ the channel frequency and $\theta$ collecting learned parameters. (2) For fixed input $\mathbf{X}$ , one-step transport $\mathbf{T}$ and decay $z$ , Exact solves for $\mathbf{Y}_{\infty}$ , with identity $\mathbf{I}$ . Sparse sums $\mathbf{Z}_{k}=z^{k}\mathbf{T}^{k}\mathbf{X}$ from depth zero through $L$ to approximate it by $\mathbf{Y}_{L}$ . (3) Either operator $\mathbf{F}$ transforms queries and keys, while V bypasses transport. GIN uses a gated Sparse residual with output $\mathbf{H}^{\prime}$ . Tiles denote features, and channel indices are suppressed.

Dataset	NoPE	WIRE	Exact	Sparse
Monochromatic-0	$0.060_{\pm 0.001}$	$0.053_{\pm 0.002}$	$\mathbf{0.044}_{\pm 0.006}$	$0.045_{\pm 0.009}$
Monochromatic-5	$0.087_{\pm 0.001}$	$0.068_{\pm 0.005}$	$\mathbf{0.036}_{\pm 0.003}$	$0.036_{\pm 0.002}$
Monochromatic-10	$0.081_{\pm 0.001}$	$0.063_{\pm 0.002}$	$\mathbf{0.027}_{\pm 0.000}$	$0.032_{\pm 0.009}$
Monochromatic-15	$0.068_{\pm 0.002}$	$0.056_{\pm 0.004}$	$\mathbf{0.026}_{\pm 0.003}$	$0.028_{\pm 0.003}$
Watts–Strogatz SPD	$0.065_{\pm 0.005}$	$0.038_{\pm 0.006}$	$\mathbf{0.016}_{\pm 0.001}$	$0.017_{\pm 0.005}$

Table 1: Synthetic graph regression. Test nRMSE

\downarrow

; published SEs, local sample SDs. Exact and Sparse use a four-layer, width-32 dense-attention GraphGPS backbone (Table G.1 ); NoPE and WIRE are published reference means under this protocol [ 11 ] . Bold compares the matched pair.

Method	Endpoint	Attention
Mixing (Zero)	$50.00_{\pm 0.00}$	$97.92_{\pm 1.77}$
WIRE	$50.00_{\pm 0.00}$	$82.43_{\pm 0.75}$
WIRE + mixing	$50.00_{\pm 0.00}$	$93.89_{\pm 6.97}$
Dynamic local gradient	$49.99_{\pm 0.02}$	$\mathbf{100.00}_{\pm 0.00}$
Sparse AW, phases zeroed	$50.00_{\pm 0.00}$	$50.00_{\pm 0.00}$
Exact AW, phases zeroed	$50.00_{\pm 0.00}$	$50.00_{\pm 0.00}$

Table 3: Constructed route-interference task. Test accuracy (%), mean ±SD over five runs. Endpoint reads a marked node after transport; Attention uses one full block. Truncated walks use

L=8

z=0.8

; Exact uses the complete resolvent. Protocol in Appendix I.2 .

Figure 5: Approximation at all 30 trained runs. Columns are the five tasks. Rows are relative output and local VJP error. Each curve compares Sparse with Exact at identical parameters and local inputs. Thin lines retain all three seeds, and thick lines average seed-level context and probe means. Values below

10^{-16}

use a plotting floor. Full settings: Appendix E.1 .

Appendix figures & tables23 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$N,M$	number of nodes and directed edges
$\mathbf{P}$	row-normalized nonnegative transition
$a_{uv}$	antisymmetric directed-edge displacement
$\omega$	rotary frequency of one complex channel
$\mathbf{T}_{\omega}$	$\mathbf{P}$ lifted by $\mathrm{e}^{\mathrm{i}\omega a_{uv}}$
$z$	geometric walk-decay factor in $[0,1)$

Appendix

Table C.1 : Notation used in the derivations.

Identity	Maximum error
Gradient operator factorization	$1.11\times 10^{-16}$
Gradient resolvent factorization	$4.44\times 10^{-16}$
Gauge covariance, operator	$1.31\times 10^{-16}$
Gauge covariance, resolvent	$4.48\times 10^{-16}$
Gauge-invariant magnitude	$4.44\times 10^{-16}$
Permutation equivariance	$1.49\times 10^{-15}$

Appendix

Table D.1 : Maximum absolute discrepancies in the independent numerical identity audit.

Figure D.1 : Deterministic Exact -AW versus sparse-AW diagnostics on a fixed graph, input, and linear readout, in double precision. Left: maximum complex-feature error relative to the complete output. Right: relative Euclidean error of the readout gradient jointly with respect to inputs, edge displacements, frequencies, edge weights, and decay. Each curve changes only

L

at the indicated

z

; 32 configurations including

L=0

are audited. These are operator/derivative checks, not trained-model comparisons. Near-unit decay requires greater depth; numerical floors need not decrease monotonically.

		Exact AW-RoPE		Sparse AW-RoPE
Dataset	Seed	Test nRMSE	Epoch	Test nRMSE	Epoch
Monochromatic-0	0	0.040	224	0.040	224
Monochromatic-0	1	0.040	219	0.039	219
Monochromatic-0	2	0.051	212	0.055	215
Monochromatic-5	0	0.035	195	0.035	230
Monochromatic-5	1	0.034	214	0.035	208

Appendix

Table E.1 : Every run in the completed Exact – Sparse study. Test nRMSE is paired with the best validation epoch (zero-based); lower is better. No run is removed. Three-decimal values are displayed here; the artifact retains full precision.

		Training epoch (s)		Peak allocated (MiB)
Dataset	$L$	Exact	Sparse	Exact	Sparse
Monochromatic-0	8	$16.659_{\pm 0.253}$	$22.974_{\pm 0.310}$	$157.676_{\pm 0.000}$	$135.950_{\pm 0.000}$
Monochromatic-5	16	$16.572_{\pm 0.075}$	$34.561_{\pm 0.140}$	$156.801_{\pm 0.000}$	$161.184_{\pm 0.000}$
Monochromatic-10	16	$16.615_{\pm 0.190}$	$34.641_{\pm 0.920}$	$155.925_{\pm 0.000}$	$153.277_{\pm 0.000}$
Monochromatic-15	8	$17.273_{\pm 1.044}$	$22.980_{\pm 0.082}$	$155.050_{\pm 0.000}$	$123.479_{\pm 0.000}$
Watts–Strogatz SPD	8	$16.932_{\pm 0.229}$	$23.355_{\pm 0.154}$	$107.952_{\pm 0.000}$	$107.347_{\pm 0.000}$

Appendix

Table E.2 : Isolated full-model H200 cost for the matched synthetic study. Entries are three-decimal mean and sample SD over three timing repeats.

L

is the Sparse depth; Exact is untruncated. Smaller is better.

Task	Checkpoint origin	$L=8$	$L=16$	$L=32$	$L=64$
M0	Exact-trained	$(7.244_{\pm 3.230})\times 10^{-3}$	$(1.971_{\pm 1.284})\times 10^{-4}$	$(2.545_{\pm 2.514})\times 10^{-7}$	$(8.153_{\pm 12.055})\times 10^{-13}$
M0	Sparse-trained	$(6.738_{\pm 3.501})\times 10^{-3}$	$(2.095_{\pm 1.904})\times 10^{-4}$	$(4.470_{\pm 6.379})\times 10^{-7}$	$(3.682_{\pm 6.271})\times 10^{-12}$
M5	Exact-trained	$(6.530_{\pm 4.548})\times 10^{-2}$	$(8.044_{\pm 6.941})\times 10^{-3}$	$(1.399_{\pm 1.465})\times 10^{-4}$	$(5.112_{\pm 6.865})\times 10^{-8}$
M5	Sparse-trained	$(5.961_{\pm 4.192})\times 10^{-2}$	$(7.044_{\pm 6.310})\times 10^{-3}$	$(1.247_{\pm 1.407})\times 10^{-4}$	$(6.065_{\pm 8.981})\times 10^{-8}$
M10	Exact-trained	$(1.014_{\pm 0.126})\times 10^{-1}$	$(1.539_{\pm 0.193})\times 10^{-2}$	$(4.049_{\pm 0.313})\times 10^{-4}$	$(3.794_{\pm 1.652})\times 10^{-7}$
M10	Sparse-trained	$(1.075_{\pm 0.081})\times 10^{-1}$	$(1.743_{\pm 0.246})\times 10^{-2}$	$(5.857_{\pm 2.700})\times 10^{-4}$	$(1.281_{\pm 1.553})\times 10^{-6}$

Appendix

Table E.3 : Relative output error at trained checkpoints. Means and sample SDs across all three run-level context averages, with three-decimal mantissas. These are approximation errors, not nRMSE or errors between independently trained models.

Nodes/graph	Method	$L$	Forward ms	Backward ms	Total ms	Peak MiB
64	NoPE	–	$1.430_{\pm 0.054}$	$1.276_{\pm 0.049}$	$2.706_{\pm 0.101}$	$99.006_{\pm 0.000}$
64	WIRE	–	$1.621_{\pm 0.018}$	$1.577_{\pm 0.024}$	$3.198_{\pm 0.038}$	$99.195_{\pm 0.000}$
64	Exact AW-RoPE	–	$3.133_{\pm 0.068}$	$2.460_{\pm 0.065}$	$5.593_{\pm 0.127}$	$218.241_{\pm 0.000}$
64	Sparse AW-RoPE	16	$3.495_{\pm 0.094}$	$6.096_{\pm 0.214}$	$9.591_{\pm 0.306}$	$180.102_{\pm 0.000}$
128	NoPE	–	$1.469_{\pm 0.049}$	$1.311_{\pm 0.033}$	$2.780_{\pm 0.082}$	$101.854_{\pm 0.000}$
128	WIRE	–	$1.591_{\pm 0.056}$	$1.566_{\pm 0.031}$	$3.157_{\pm 0.073}$	$102.231_{\pm 0.000}$

Appendix

Table F.1 : Matched learnable positional-layer cost on H200. ReLU linear attention, batch size eight, width 64, four heads,

z=0.8

. Forward/backward times and peak allocated memory are summarized over three independent repeats, each averaging ten warmed steps. Exact is untruncated; Sparse uses

L=16

. All values have three decimals. All 72 small-graph cells (including the companion FAVOR+ table) are complete. The 256-node Exact timing jump is discussed below.

Nodes	Method	$L$	Forward ms	Backward ms	Total ms	Peak MiB
64	NoPE	–	$1.532_{\pm 0.035}$	$1.511_{\pm 0.037}$	$3.043_{\pm 0.068}$	$99.702_{\pm 0.000}$
64	WIRE	–	$2.009_{\pm 0.513}$	$1.753_{\pm 0.023}$	$3.762_{\pm 0.492}$	$99.891_{\pm 0.000}$
64	Exact AW-RoPE	–	$3.717_{\pm 0.825}$	$2.703_{\pm 0.018}$	$6.420_{\pm 0.834}$	$218.241_{\pm 0.000}$
64	Sparse AW-RoPE	16	$3.799_{\pm 0.213}$	$6.618_{\pm 0.467}$	$10.417_{\pm 0.678}$	$180.797_{\pm 0.000}$
128	NoPE	–	$1.565_{\pm 0.023}$	$1.543_{\pm 0.004}$	$3.108_{\pm 0.019}$	$103.246_{\pm 0.000}$
128	WIRE	–	$1.708_{\pm 0.008}$	$1.774_{\pm 0.020}$	$3.482_{\pm 0.015}$	$103.622_{\pm 0.000}$

Appendix

Table F.2 : Companion softmax FAVOR+ positional-layer timings. Protocol, hardware, initialization and reporting match the ReLU measurements in Table F.1 . Entries are mean ±SD , three decimals; Exact is untruncated.

Hyperparameter	Value
Backbone layers	4
Hidden width	32
Attention heads	1
Dropout	0.2
Batch size	16
Attention	full

Appendix

Table G.1 : Shared hyperparameters of the matched synthetic study (Section 4.2 ). Both Exact and Sparse arms use these settings with matched initializations.

Dataset	Method	LR	$L$	$z$	Validation
Mono-0	NoPE	$1\mathrm{e}{-4}$	–	–	0.046553
Mono-0	AW	$2\mathrm{e}{-4}$	16	0.6	0.031604
Mono-0	AW-NB	$2\mathrm{e}{-4}$	16	0.8	0.029987
Mono-0	AW-NB-MS	$2\mathrm{e}{-4}$	8	0.8	0.032441
Mono-5	NoPE	$2\mathrm{e}{-4}$	–	–	0.044055
Mono-5	AW	$2\mathrm{e}{-4}$	16	0.8	0.026159

Appendix

Table G.2 : Validation-selected configurations in the completed GIN synthetic grid. Metric is normalized RMSE (lower is better).

Dataset	GIN-NoPE	GIN-AW-RoPE	GIN-AW-NB	GIN-AW-NB-MS	Winner
Monochromatic-0	$0.047_{\pm 0.000}$	$0.035_{\pm 0.001}$	$\mathbf{0.034_{\pm 0.002}}$	$0.036_{\pm 0.002}$	AW-NB
Monochromatic-5	$0.041_{\pm 0.000}$	$\mathbf{0.026_{\pm 0.001}}$	$0.031_{\pm 0.001}$	$0.032_{\pm 0.005}$	AW
Monochromatic-10	$0.034_{\pm 0.000}$	$\mathbf{0.020_{\pm 0.000}}$	$0.022_{\pm 0.001}$	$0.022_{\pm 0.000}$	AW
Monochromatic-15	$0.024_{\pm 0.000}$	$\mathbf{0.016_{\pm 0.000}}$	$0.016_{\pm 0.000}$	$0.016_{\pm 0.000}$	AW
Watts–Strogatz SPD	$0.013_{\pm 0.001}$	$\mathbf{0.006_{\pm 0.001}}$	$0.007_{\pm 0.002}$	$0.011_{\pm 0.001}$	AW

Appendix

Table G.3 : GIN synthetic confirmation. Test nRMSE

\downarrow

, mean ±SD over two matched runs after 250 epochs, with configurations frozen from the validation-only grid. Bold marks the lowest unrounded mean.

Injection	Validation $\uparrow$	Test $\uparrow$	$\Delta$
NoPE	$0.4487{\pm}0.0286$	$0.4502{\pm}0.0276$	–
AW-RoPE ReZero	$\mathbf{0.6457{\pm}0.0022}$	$\mathbf{0.6461{\pm}0.0024}$	$+0.1959$
AW-RoPE ReZero + norm.	$0.6265{\pm}0.0057$	$0.6263{\pm}0.0057$	$+0.1762$
AW-RoPE Single + norm.	$0.5402{\pm}0.0128$	$0.5382{\pm}0.0138$	$+0.0880$

Appendix

Table G.4 : AW-RoPE Cluster stability ablation, four matched runs. All arms are paired and budget-matched. This table isolates Sparse AW-RoPE injection.

\Delta

is relative to NoPE test accuracy.

Figure H.1 : Prediction and circulation under different edge fields. Top: paired test metrics at each validation-best checkpoint, mean and sample SD over three runs. Bottom: one point per run, obtained by averaging raw fundamental-cycle RMS across insertion layers with cycles in the first validation batch. The symmetric-log axis retains exact zeros. The one unrestricted Monochromatic-0 run is flat on this diagnostic batch.

Figure H.2 : Exploratory $L\times z$ sensitivity, fixed run. Each cell shows the best validation score of one run, to three decimals. Color scales are independent across tasks. Brighter cells indicate better scores. All 27 cells are retained, including the three reused mechanism cells.

Dataset	Method	Train s/epoch	Peak GiB	Loader s
Monochromatic-0	NoPE	$7.818_{\pm 0.076}$	$0.097_{\pm 0.000}$	$8.601_{\pm 0.049}$
Monochromatic-0	WIRE	$10.292_{\pm 0.535}$	$0.098_{\pm 0.000}$	$8.580_{\pm 0.047}$
Monochromatic-0	AW-RoPE, $L=4$	$16.548_{\pm 0.202}$	$0.115_{\pm 0.000}$	$8.807_{\pm 0.102}$
Monochromatic-0	AW-RoPE, $L=8$	$21.516_{\pm 0.115}$	$0.130_{\pm 0.000}$	$8.730_{\pm 0.295}$
Monochromatic-0	AW-RoPE, $L=16$	$31.770_{\pm 0.365}$	$0.159_{\pm 0.000}$	$8.789_{\pm 0.196}$
Peptides-struct	NoPE	$3.493_{\pm 0.043}$	$2.801_{\pm 0.026}$	$31.090_{\pm 0.673}$

Appendix

Table H.1 : Isolated H200 full-model cost. Three timing runs, mean ±SD to three decimals. Peak GiB is each run’s maximum allocated memory over its three measured epochs. Loader seconds use existing prepared caches and are listed separately. The real tasks use FAVOR+.

Panel of Figure 22 — Figure I.1 : Route phase changes transport on a fixed graph. The diamond has both edge orientations, uniform row transition weights, and a unit real input at $v$ . Arrows show walk indices from $u$ toward $v$ ; the row action gathers that input back to $u$ . Only $a_{ub}=a_{bv}=\Delta/2$ and their negatives on reversed edges vary; all other displacements are zero, with $\omega=1$ . Every displacement remains in $[-\pi,\pi]$ . At $L=2$ , the two routes have equal weight $1/4$ . AW’s normalized response power changes from reinforcement to cancellation. The dashed line is the magnitude of an endpoint-factorized coefficient with the same phase-free mixing weights, not a measured WIRE network.

Field class	Ingredients	Route	Feature-cond.
Mixing (Zero)	transport only	$\times$	$\times$ (proof)
WIRE	endpoint phases	$\times$	$\times$
Static field (random, learned)	circulation	–	$\times$ (proof)
Dynamic local gradient	adaptivity, local	$\times$	$\times$ (proof)
Dynamic nonlocal Flat	adaptivity, nonlocal	–	✓ (unstable)
Sparse AW (ours)	circulation + adaptivity	✓	✓

Appendix

Table I.1: Capability ladder on the constructed tasks. Each row adds one ingredient. Check marks solve at high accuracy, crosses sit at chance. “(proof)” marks entries covered by an impossibility statement; the route task uses endpoint readout and full networks, the feature-conditional task uses full networks on unseen sizes. The ladder compares field classes within the walk-transport operator interface; learned restriction-map transports are discussed in Appendix B.9 .

Task	Collision or empirical failure	Successful construction
Route interference, endpoint	Mixing (Zero), WIRE and pointwise gradient transport	AW route-phase interference
Feature-conditioned cycle, full block	Static shell transport and pointwise gradients; WIRE and random fixed fields fail empirically	Local edge AW or dynamically projected nonlocal Flat

Appendix

Table I.2: The two constructed tasks test different capabilities under specified readouts. These are comparison axes, not a nested hierarchy of all possible graph models.

Arm	Evaluation	20	21	22	23	24
Sparse AW	Test	100.00	100.00	100.00	93.45	99.91
Sparse AW	48/64 nodes	92.97	81.64	100.00	50.00	71.88
Dynamic nonlocal Flat	Test	99.91	100.00	99.96	74.26	100.00
Dynamic nonlocal Flat	48/64 nodes	50.78	82.81	100.00	50.00	97.27

Appendix

Table I.3: All AW and dynamic nonlocal Flat runs, accuracy (%). Test is the primary unseen-size split; 48/64 nodes is a separate extrapolation diagnostic. Zeroing phases gives

50\%

for every run on the primary test.

Figure I.2 : Learned fields and Flat run variability. (a) AW edge displacements for the first paired validation example at

n=18

. (b) The dynamic Flat control’s reconstructed zero-mean potential on that pair. Cycle indices are used only for this display, not supplied as model features. (c) All five Flat validation trajectories; the partially fitted run is highlighted. No smoothing is applied.

Dataset	Metric	WIRE	Mixing	WIRE + mixing	Sparse AW-RoPE
Monochromatic-0	nRMSE $\downarrow$	$0.073_{\pm 0.008}$	$0.044_{\pm 0.005}$	$0.045_{\pm 0.006}$	$\mathbf{0.043}_{\pm 0.006}$
Peptides-struct	MAE $\downarrow$	$0.257_{\pm 0.002}$	$0.255_{\pm 0.002}$	$0.257_{\pm 0.001}$	$\mathbf{0.253}_{\pm 0.001}$

Appendix

Table I.4 : Completed matched mixing controls. Test at validation-best, mean

{}_{\pm\mathrm{sample\ SD}}

over three matched runs, three decimals. Mixing is phase-free propagation; WIRE + mixing applies propagation before WIRE rotation. Bold marks the best unrounded mean.

Dataset	Arm	Allocated	Positional	Unused encoder
Monochromatic-0	WIRE	39644	320	0
Monochromatic-0	Mixing	39324	0	85
Monochromatic-0	WIRE + mixing	39644	320	0
Monochromatic-0	Sparse AW-RoPE	39656	332	85
Peptides-struct	WIRE	506729	1920	0
Peptides-struct	Mixing	504809	0	270

Appendix

Table I.5 : Parameter accounting for the matched mixing study. Counts are identical across the three runs of each row. Allocated includes modules whose outputs are unused. The final column identifies unused coordinate-encoder parameters.

Figure I.3 : Attention on fixed Monochromatic-0 validation examples. Left: the three categorical node colors supplied to the task. Center and right: final-layer attention probabilities from the circled node for WIRE and Sparse AW-RoPE. Rows are the first three validation graphs in their stored order. All six attention panels use one common color scale, without per-panel rescaling. Seed 0 and validation-best checkpoints are fixed.

Graph Positional Encoding

See all 15 papers

Sep 26, 2025

Rotary Position Encodings for Graphs

We study the extent to which rotary position encodings (RoPE), a recent transformer position encoding algorithm broadly adopted in large language models (LLMs) and vision transformers (ViTs), can be applied to graph-structured data. We find that rotating tokens depending on the spectrum of the graph Laplacian efficiently injects structural information into the attention mechanism, boosting performance in synthetic and real-world graph learning tasks. This approach, coined Wave-Induced Rotary Encodings (WIRE), enjoys intriguing theoretical properties: it recovers regular RoPE on grids, and depends asymptotically on the graph effective resistance. Unlike bias-based relative position encodings, WIRE is compatible with linear attention.

Isaac Reid, Arijit Sehanobish, Cederik Höfs +7

University of Cambridge · Google DeepMind · Independent Researcher +3

Graph Positional Encoding Rotary Positional Embeddings Graph Representation Learning Attention Mechanisms Graph Transformer

Ask PDF

Jun 11, 2026

Understanding Truncated Positional Encodings for Graph Neural Networks

Positional encodings (PEs) enhance the power of graph neural networks (GNNs), both theoretically and empirically. Two of the most popular families of PEs - spectral (e.g., Laplacian eigenspaces, effective resistance) and walk-based (polynomials of the adjacency matrix) - are theoretically equivalent in expressive power, with expressivity between the 1-WL and 3-WL tests. However, this equivalence assumes the GNN uses the "complete" version of these PEs, which requires

O(n^3)

time and space complexity. Instead, practitioners commonly use truncated variants of these encodings, such as the first

k

eigenspaces or powers of the adjacency matrix. However, the theoretical properties of these truncated PEs are unknown. In this work, we initiate the study of these truncated PEs. Theoretically, we show that, under truncation, several families of PEs are fundamentally different in expressive power. As a corollary, we show that truncated spectral PEs are no longer stronger than the 1-WL test. We also study a family of spectral PEs, the

k

-harmonic distances, to highlight the differences in expressive power of even closely related truncated PEs. Finally, we experimentally show that a mix of truncated PEs is preferable to any single family on real-world datasets.

James Flora, Mitchell Black, Weng-Keen Wong +1

School of Electrical Engineering and Computer Science, Oregon State University, Corvallis, Oregon, USA · Halıcıoğlu Data Science Institute, University of California San Diego, San Diego, California, USA.

GNN Expressivity Positional Encoding Graph Positional Encoding

Ask PDF

Sep 28, 2026

RoPE is Dead, Long Live RoPE: Towards Scalable Data-aware Positional Encodings

Transformers process tokens without any inherent notion of order, making positional encoding a fundamental requirement rather than an architectural refinement. Rotary Position Embedding (RoPE) has become the default positional encoding in modern language models, yet it is heavily biased toward nearby tokens. Existing alternatives have been evaluated under different settings, leaving the literature fragmented and without a clear replacement. We bring structure to this landscape by examining a specific weakness of RoPE: its slow frequency bands, whose wavelengths exceed the training context and expose models to unseen angles during extrapolation. We therefore introduce Data aware RoPE (DaRoPE), which preserves standard RoPE on the fast bands but replaces absolute position on the slow bands with bounded coordinates learned from contextual representations. Therefore, the slow-band geometry depends on the data rather than only on positional distance. We compare representative encodings under matched conditions across synthetic tasks, symbolic music, genomics, neural signals, and language models spanning 124M to 50B parameters. Across these experiments, DaRoPE leads on non-text benchmarks, mitigates recency bias, while remaining best or on par in language modeling and length extrapolation. Moreover, the learned coordinates also make the mechanism interpretable, revealing how attention layers leverage contextual information beyond token distance. Together, these results support DaRoPE as the best overall default among the evaluated methods, when there is no domain-specific reasons to prefer another.

Jarod Lévy, Mathurin Videau, Jad Yehya +3

Meta AI, Paris · Inria, Université Paris-Saclay, Palaiseau, France

Rotary Positional Embeddings Long-Context Language Modeling Positional Encoding Representation Geometry in Language Models

Ask PDF

Abstract

Graph Positional Encoding

Explore similar work

Rotary Position Encodings for Graphs

Understanding Truncated Positional Encodings for Graph Neural Networks

RoPE is Dead, Long Live RoPE: Towards Scalable Data-aware Positional Encodings