Disentangling the Expressivity of RoPE

Published as a conference paper at COLM 2026

Disentangling the Expressivity of RoPE Selim Jerad1 Anej Svete2 Jiaoda Li2 Ryan Cotterell2 Toyota Technological Institute at Chicago1 ETH Zürich2 sjerad@ttic.edu {anej.svete, jiaoda.li, ryan.cotterell}@ethz.ch

arXiv:2608.11909v1 [cs.LG] 12 Aug 2026

Abstract Two accounts recur in explanations of the success of rotary position embeddings (RoPE). Expressivity studies associate periodic position information with modular predicates, whereas mechanistic and long-context studies emphasize positional anchors and local offsets. We formalize both accounts for fully uniform, finite-precision soft-attention transformers. We find that, if every rotary component is periodic, RoPE transformers recognize exactly the languages definable in past temporal logic with modular predicates. Conventional RoPE is different: The rotations it computes never repeat. This yields a precision-dependent bounded simulation of fixed-offset lookback operators, rather than an all-length modular characterization. Controlled experiments match this separation: Constructed periodic schedules length-generalize on modular languages, while conventional RoPE behaves more like a bounded locality bias and can impair tasks requiring positioninvariant access to distant context. Altogether, our findings shed light on RoPE transformers, bringing theoretical expressivity characterizations closer to models used in practice.

1

Introduction

In the absence of positional information, self-attention—the core operation of transformers (Vaswani et al., 2017)—is permutation-equivariant. Positional encodings (PEs) help distinguish symbol positions. The original transformer employs sinusoidal PEs (SiPE), which add position-dependent sine and cosine features to symbol representations. However, models using SiPE often generalize poorly to sequences longer than those seen during training (Rosendahl et al., 2019; Neishi & Yoshinaga, 2019; Press et al., 2022). Motivated by this limitation, RoPE was proposed as an alternative that encodes relative positions within attention: It rotates query and key vectors as a function of position, making their dot product depend on relative displacement (Su et al., 2023). RoPE has since become the de facto PE scheme in transformer-based LMs (Bai et al., 2023; Grattafiori et al., 2024; Team et al., 2024; Olmo et al., 2025; Yang et al., 2025a; DeepSeek-AI et al., 2026, inter alia). Despite its widespread use, the theoretical contributions of RoPE remain unclear. Existing explanations fall broadly into two themes. Theoretical expressivity work links the periodicity of sinusoidal functions to modular predicates in formal logic (Yang et al., 2024; 2025b). More practically oriented analyses find that the apparent length generalization ability of RoPE can be superficial: RoPE may extrapolate to longer sequences without enabling effective use of distant context (Kazemnejad et al., 2023; Men et al., 2024; Gelberg et al., 2025; Du et al., 2026). A complementary, more mechanistic line of work instead emphasizes its role as a positional anchor and its bias toward fixed local offsets (Barbero et al., 2025a;b). These perspectives prima facie appear incompatible. We reconcile them within the fully uniform fixed-precision transformer framework. We show that component-periodic RoPE (RoPEP ) is equivalent to past temporal logic with modular predicates, LTL[P, MOD]. Conventional RoPE, in contrast, realizes a non-periodic schedule. The two variants differ only in the angles they rotate by. RoPEP rotates the key and query subspaces by rational multiples 1

Published as a conference paper at COLM 2026

LTL[S]: Rightmost hard attention

LTL[S, MOD]: Rightmost hard-attention + SiPEP Yang et al. (2024)

Yang et al. (2024)

PARITY

( ab)∗ Σ∗ abΣ∗

LTL[P]: Soft attention Li & Cotterell (2025)

a∗

LTL[P, MOD]: RoPEP / SiPEP attention Thm. 3.1, Thm. 3.2

( aa)∗

Figure 1: The expressivity landscape of fully uniform finite-precision transformers. The red box shows our contributions: The connection of RoPEP and SiPEP transformers to LTL[P, MOD], which is incomparable with LTL[S] (capturing rightmost hard-attention NoPE transformers). Their intersection contains LTL[P], corresponding to soft-attention NoPE transformers. of 2π, so each rotary component cycles through finitely many phases and repeats with a fixed period, which a fixed-precision model can realize by a lookup table indexed by the position modulo that period. Conventional RoPE instead rotates by frequencies whose phases are incommensurate with 2π and therefore never repeat (§2.4). Its relative scores can simulate the look-back of k steps, only while a precision-dependent score gap is maintained. This connects RoPE to local attention (Li & Cotterell, 2026) and gives a formal account of fixed-offset heads observed in practice (Barbero et al., 2025a). Fig. 1 summarizes the landscape of fully uniform finite-precision transformers. We vet our results experimentally by training transformers on controlled formal languages. We find that constructed periodic RoPE schedules length-generalize on languages requiring modular predicates. In contrast, no conventional base value generalizes on ( aa)∗ or ( ab)∗ , suggesting that changing the base does not recover the modular construction. Across the same sweep, the mean longest-perfect length of conventional RoPE outperforms NoPE at six of seven bases on an LTL[Y] language, but underperforms at every base on both an LTL[P] language and a language requiring both P and Y. These results support the locality account while suggesting that the resulting local bias can interfere with long-distance conditioning.

2

Preliminaries

An alphabet Σ is a finite, non-empty set of symbols and Σ∗ denotes the set of all strings over Σ. With | · |, we denote the length of a string—in particular, we write |w1 · · · w N | = N. We write ε for the empty string, the unique string of length 0. A formal language L over Σ is a subset of Σ∗ . 2.1

Linear Temporal Logic

Regular languages are languages that can be described by regular expressions; see §A.3 for details. Subclasses of regular languages can equivalently be described with different formalisms such as automata and logic. Past work (Yang et al., 2024; Li & Cotterell, 2025; Jerad et al., 2025) links finite-precision transformers with subregular classes of languages. We use linear temporal logic (LTL) as our primary descriptive formalism. Given w = w1 · · · w N , LTL formulas are evaluated at a position i; a formula accepts w when it holds at the readout position N + 1. The atomic predicate π a (i ) tests whether the symbol wi at position i matches a. Furthermore, LTL leverages temporal operators to evaluate context-dependent properties at positions. The operators we need are the following: w, i |= Pψ ⇐⇒ ∃ j < i : w, j |= ψ,

w, i |= Yψ ⇐⇒ i > 1 ∧ w, i − 1 |= ψ. 2

(1)

Published as a conference paper at COLM 2026

For k ≥ 1, we write Yk ψ for k-fold composition of Y; equivalently, w, i |= Yk ψ if and only if i > k and w, i − k |= ψ. We write LTL[P] and LTL[P, Y] for the fragments generated from these operators, atomic predicates, and Boolean connectives. The detailed LTL semantics and equivalent first-order, automata, and algebraic formalisms appear in §A. A third operator, S (“since”), subsumes both P and Y (Gabbay et al., 1980), so LTL[S] is all of LTL—exactly the star-free languages (Kamp, 1968; McNaughton & Papert, 1971). We use first-order logic over the linear order < interchangeably with LTL, via LTL[S] = FO[<] (Kamp, 1968) and LTL[P] = PFO2 [<], the past fragment of the two-variable logic FO2 [<] (Li & Cotterell, 2025); §A.2 gives the formal definitions. Modular predicates. The unary predicate MODrm (i ) holds exactly when i ≡ r (mod m). We write LTL[P, MOD] for LTL[P] augmented with all such predicates. Adding modular predicates preserves the LTL–FO[<] correspondence: LTL[P, MOD] = PFO2 [<, MOD] (Thm. 3.3). 2.2

Transformers

A consistent takeaway of theoretical work is that transformers’ computational abilities heavily depend on the modeling assumptions one makes (Hao et al., 2022; Jerad et al., 2025; Svete et al., 2026). Understanding the minimal viable definition of a transformer is particularly useful, as it facilitates the analysis of the fundamental components of every transformer. To this end, we adopt the fully uniform fixed-precision model of Li & Cotterell (2025). Uniformity requires all strings be processed by a model defined by a single set of parameters, in contrast to having a separate model for each length. def

Finite precision. Transformer parameters and activations belong to a finite set F = { f 1 , . . . , f K }, corresponding to real-world transformers (e.g., 32-bit floating-point arithmetic). All computations are performed rounded to F, with ∞ and −∞ in F which describe  overflow. We denote by f large the smallest positive element of F such that exp − f large rounds to 0. This permits exact hard selection whenever the winning score exceeds every alternative by at least f large .

Transformers as string classifiers. We study transformers as string classifiers. An input to a transformer is a string w ∈ Σ∗ augmented with the beginning-of-string BOS and enddef of-string EOS symbols, BOS w EOS. We set Σ = Σ ∪ { BOS, EOS }. An initial embedding layer maps symbols in Σ to distinct elements of FD , where D ∈ N is the hidden state size. The embedding layer is followed by a stack of L transformer layers, each composed of an attention layer, a feedforward network, and layer-normalization. For a layer ℓ and position i, xiℓ ∈ FD is the contextual representation of symbol wi after being processed by layer ℓ. We denote by λ : (Σ)∗ → (FD )∗ the function that maps an input BOS w EOS to contextual representations through the embedding layer and the L transformer layers. For a string w and string position i, we denote by λ(w)i ∈ FD the final i’th contextual representation xiL . To enable language recognition, λ is paired with an output classification layer F : (FD ) → def {0, 1} acting on λ(w)EOS for an input w. Given a precision regime F, the tuple T = (λ, F ) def is an F-transformer and defines a language L(T) = {w | F (λ(w) EOS ) = 1}. Soft attention. We assume soft attention, which corresponds to standard implementations. We note a minute but important practical detail: For numerical stability, soft attention is usually computed by subtracting from Si,j —the attention score between the query qi and the key k j —the maximum score. We define the normalized score αi,j as follows:
exp Si,j − maxk<i Si,k αi,j = i−1 . (2) ∑l =0 exp (Si,l − maxk<i Si,k ) These NoPE transformers (SMAT) recognize exactly LTL[P] = PFO2 [<] (Li & Cotterell, 2025). 3

Published as a conference paper at COLM 2026

2.3

Rotary Position Embeddings

RoPE (Su et al., 2023) partitions the query’s and key’s D-dimensional space into twodimensional subspaces and rotates each by an angle that depends on the absolute position i. Concretely, let     def def cos (θi ) − sin (θi ) RΘ,i = diag Rotθ1 ,i , . . . , RotθD/2 ,i , Rotθ,i = (3) sin (θi ) cos (θi ) where RΘ,i is a block-diagonal matrix and Θ ∈ [0, 2π ] D/2 is a tuple of angles assigned to the different two-by-two rotation matrices in RΘ,i , which we call the schedule. When the schedule is implicit, we drop it from the subscript and write, e.g., Ri ; we restore it whenever several schedules are in play. In conventional implementations, the angular frequencies are parameterized as θd = β−2(d−1)/D , where β > 0 is called the base; the original RoPE construction uses β = 104 (Su et al., 2023). At position i, queries and keys become
qi = RΘ,i Qxi + bq ,

ki = RΘ,i (Kxi + bk ) .

(4)

For exact rotations and zero biases, orthogonality gives the relative-position identity k⊺j qi = ( RΘ,j Kx j )⊺ RΘ,i Qxi = x⊺j K ⊺ ( RΘ,j )⊺ RΘ,i Qxi , = x⊺j K ⊺ RΘ,i− j Qxi ,

(5)

making the score depend on the distance i − j. Ideal and realized rotations. The rotation above is ideal: It is evaluated in exact arithmetic, and it stores real numbers. A fixed-precision model computes something else. It stores a b and evaluates the rotation with the finite-precision arithmetic. We write R bb ∈ schedule Θ Θ,i b (d) ∈ F2×2 FD× D for the realized matrix in finite-precision arithmetic at position i, and R b Θ,i

for its dth block. The hat marks the realized map as opposed to the ideal one i 7→ RΘ,i . The distinction matters because rounding need not preserve the structure of the ideal map; our periodicity definitions concern the realized map. Custom schedules and unrotated subspaces. To establish lower bounds for RoPE transformers, we permit a custom schedule—a bespoke set of angles Θ chosen for the target language. Custom schedules are standard in expressivity literature (e.g., Chiang et al., 2023; Yang et al., 2024; 2025b). We also allow unrotated subspaces with θd = 0; these subsume partial-RoPE variants (Barbero et al., 2025b; Yang et al., 2025c; Khan et al., 2026) and retain the LTL[P] computation available to NoPE, while separate rotary dimensions supply modular or fixed-offset information. 2.4

Component-Periodic and Non-Periodic RoPE

Intuitively, PEs with periodicity behave similarly to modular positional predicates in logic (Chiang et al., 2023; Yang & Chiang, 2024; Yang et al., 2025b). We formalize this intuition b i and R b (d) are the realized for finite-precision RoPE, with the proofs in §C.1. Throughout, R i

matrix and its dth block. b is Definition 2.1 (Component-periodic and non-periodic RoPE). A realized RoPE schedule Θ component-periodic if, for every d, there is an integer md ≥ 1 such that b (d) = R b (d) R i +m i

for all i ∈ N.

d

(6)

It is non-periodic if this condition fails: Some component has no positive integer period. bi. Because D is fixed, component-periodicity is equivalent to periodicity of the full map i 7→ R def b i+ M = R b i for every i, with unrotated blocks In particular, M = lcm (m1 , . . . , m D/2 ) satisfies R having period 1. We denote by SMAT[RoPEP ] and SMAT[RoPENP ] the class of languages 4

Published as a conference paper at COLM 2026

recognized by fixed-precision component-periodic and non-periodic RoPE transformers, respectively. We show that periodic schedules can be expressed via finitely many modular predicates: b is componentProposition 2.1 (Component-periodicity via MOD). If a realized RoPE schedule Θ periodic, then its image is finite and, for every matrix coordinate and realized value, the positions attaining that value are definable by unary modular predicates. A standard class of periodic schedules is the set of rational multiples of π (Yang et al., 2024). Proposition 2.2 (Rational-angle functions are periodic). If θd / (2π ) = ad /md ∈ Q, then i 7→ Rotθd ,i has period md . Intuitively, adding md to i changes the phase by 2πad . Prop. 2.2 concerns the ideal map, and it may not transfer to finite precision. The position i grows without bound as the string does, so neither i nor the phase θd i stays representable in F at all lengths. An implementation that forms the phase and then rounds therefore computes a map that need not agree with Rotθd ,i , and that realized map need not repeat. Rational angles alone thus do not make a schedule component-periodic in the sense of Def. 2.1. We resort to realizing the same rational-angle function without forming the product θd i. For θd = 2πad /md , we precompute the finite table
def Td (r ) = roundF Rotθd ,r , 0 ≤ r < md , (7) b (d) = Td (i mod md ). The table has md entries and define the realized block directly by R i and the counter has md states, and both depend on the schedule but not on the input length, so the construction stays inside the fully uniform fixed-precision model. The realized map b (d) = R b (d) for every i by construction. Similar cyclic lookups appear in then satisfies R i +md

i

practice. Huo (2026) precomputes one period of P-RoPE and indexes it by position modulo the period. Wang et al. (2024) round each RoPE wavelength to the nearest integer, so that every component repeats after a whole number of positions. Both were introduced to improve length generalization, and both are component-periodic in the sense of Def. 2.1, so the characterization we prove next applies to them directly.

3

A Characterization of SMAT[RoPEP ]

This section describes the equivalence of SMAT[RoPEP ] with LTL[P, MOD] = PFO2 [<, MOD]. The next two subsections sketch the intuition for the lower and upper bounds; full proofs are in §C. Theorem 3.1. SMAT[RoPEP ] = LTL[P, MOD] = PFO2 [<, MOD]. 3.1

From SMAT[RoPEP ] to PFO2 [<, MOD]

Let M be the common period to all the rotation matrices in the block diagonal matrix (§2.4). Then, every realized entry depends only on i mod M, so equality to any realized value is a finite disjunction of predicates MODrM (i ) (Prop. 2.1). The fixed-precision simulation of all remaining transformer operations by PFO2 [<] (Li & Cotterell, 2025) then gives SMAT[RoPEP ] ⊆ PFO2 [<, MOD]. Lemma 3.1. Any F-transformer with RoPEP can be simulated by PFO2 [<, MOD]. SMAT[RoPEP ] ⊆ PFO2 [<, MOD] = LTL[P, MOD].

Hence,

RoPE as a unary predicate. Although RoPE scores encode pairwise distances, it does not require binary primitives; unary ones suffice. To see why, consider the binary modular predicate MODrm (i, j) = ⊤ ⇐⇒ ( j − i ) ≡ r (mod m), (8) 5

Published as a conference paper at COLM 2026

which models the relative position dependency of RoPE by passing the distance between two positions through a periodic function. We show in §C.2 that the binary modular predicate can be expressed by a Boolean combination of unary modular predicates. Proposition 3.1. Binary modular predicates can be expressed with unary modular predicates and Boolean logic. 3.2

From LTL[P, MOD] to SMAT[RoPEP ]

For the reverse inclusion, F-transformers with RoPEP can first implement Boolean connectives and P in unrotated dimensions via structural induction (Li & Cotterell, 2025). For each modular atom MODrm (i ), a period-m rotary pair uses the lookup table Tm (s) = Rot2π/m,s for 0 ≤ s < m and returns Tm (i mod m). An attention head compares the returned phase with the fixed BOS phase. A constant non-BOS baseline separates the matching residue from every nonmatching residue, and stable softmax turns the comparison into an exact Boolean value. Thus LTL[P, MOD] ⊆ SMAT[RoPEP ]. Lemma 3.2. For every LTL[P, MOD] formula, there is an F-transformer with RoPEP that simulates the formula. Hence LTL[P, MOD] ⊆ SMAT[RoPEP ]. Connection to attention sinks. The use of BOS as a fixed anchor connects the tightness construction to attention sinks, where language models allocate disproportionate attention to initial tokens (Xiao et al., 2024). One account of why sinks are useful is that they prevent contextual representations from over-mixing and keep them sufficiently distinct (Barbero et al., 2025b). Our construction offers a complementary reason: The anchor is what makes unary modular predicates computable, because the query’s phase must be compared against a key whose own phase does not move. This suggests that sinks in RoPE transformers serve in part to expose positional phase, and we note that Gemma 7B, which uses RoPE, does concentrate attention on BOS (Barbero et al., 2025a). 3.3

Periodic Sinusoidal Positional Encodings

We find absolute sinusoidal PEs (Vaswani et al., 2017) to be equivalent to RoPEP . As for RoPEP , we denote by SiPEP the class of periodic sinusoidal encodings such that the realized sinusoidal position-to-embedding map has a finite integer period as in Def. 2.1. We similarly define SiPENP . Theorem 3.2. SMAT[SiPEP ] = LTL[P, MOD] = PFO2 [<, MOD]. The proof (§C.4) again expresses the finite periodic image with modular predicates and uses custom periodic features to recover each modular atom. This shows that the key factor for the corresponding all-length logical class is the periodicity of the encoding; both the absolute and relative encodings are unified under modular predicates. 3.4

Characterizing LTL[P, MOD]

We have established that SMAT[RoPEP ] and SMAT[SiPEP ] can both be exactly characterized by LTL[P, MOD]. To better grasp the expressive power of RoPEP and SiPEP , we provide additional characterizations of LTL[P, MOD]. Building on Dartois & Paperman (2013); Li & Cotterell (2025), we prove the following equivalences1 in §B. Theorem 3.3. Let L ⊆ Σ∗ be a regular language, M be its syntactic monoid, and A be the minimal DFA accepting it. The following assertions are equivalent: (i) L is a left-deterministic modular polynomial (ii) M ∈ QR (iii) ∃k ∈ N such that Ak is partially ordered (iv) L = L(ϕ) for some PFO2 [<, MOD] formula ϕ (v) L = L(ψ) for some LTL[P, MOD] formula ψ 1 The relevant formal language theory tools are properly introduced in §A.

6

Published as a conference paper at COLM 2026

Language

Defining property

Class

Account

( aa)∗ ( ab)∗ aΣ∗ Σ∗ a Σ∗ abΣ∗

even length ab repeated starts with a ends with a contains ab

LTL[P, MOD]; not star-free LTL[P, MOD]; not LTL[P] LTL[P] LTL[Y]; not LTL[P] LTL[P, Y]; locally testable

modular modular locality locality locality

Table 1: The formal languages we train on, each over an alphabet Σ with |Σ| > 1. The last column records which account the language probes: the modular account of §3 or the locality account of §4. §E.1 gives the full definitions. The characterization provides novel tools for (in)expressibility statements about LTL[P, MOD]. We can first show via PFO2 [<, MOD] that LTL[P, MOD] can leverage modular predicates to recognize languages with a periodic behavior where a substring is repeated indefinitely. Proposition 3.2. For every nonempty word w1 · · · wm , the language (w1 · · · wm )∗ belongs to PFO2 [<, MOD]. Proof. It is defined by MOD0m ∧ ∀i

V

 0≤ j < m

 j MODm (i ) ⇒ πw j (i ) , which is in PFO2 [<, MOD].

■

Importantly, Prop. 3.2 implies that languages such as ( ab)∗ and ( aa)∗ belong to PFO2 [<, MOD], leading to the following conclusions. LTL[P, MOD] and LTL[S] are incomparable. In other words, neither class contains the other. In one direction, ( aa)∗ is not star-free (Yang et al., 2024) and so lies outside LTL[S], yet Prop. 3.2 places it in LTL[P, MOD]. In the other direction, LTL[S] can recognize the locally testable languages (Zalcstein, 1972)—those that require checking that a finite sequence of symbols occur at consecutive positions. Written in LTL, this needs the Y operator: Σ∗ abΣ∗ is defined by P (πb ∧ Yπ a ). The only temporal operator of LTL[P, MOD] is P, which cannot step to an adjacent position, and we show in §B.1 that LTL[P, MOD] contains no such language. LTL[P, MOD] cannot perform modular counting. Modular predicates count positions, not symbols. Adding them to LTL[P] therefore does not let it decide whether the number of occurrences of a symbol is divisible by an integer. The canonical example is PARITY, the set of bitstrings with an even number of 1s. We prove in §B.1 that PARITY is not LTL[P, MOD]. 3.5

Testing the Modular Account

We train transformer classifiers on the languages in Tab. 1, which also records the account each language probes. Training strings have length at most 40; test strings have lengths 41–500. Every configuration is run over 5 seeds and 3 learning rates, and every conventionalschedule configuration is fully rotated. Besides accuracy, we report the longest perfect length N ∗ : the largest N for which accuracy is 100% at every tested length through N. §E gives the architecture and optimization settings and reports per-run means and standard deviations. Tab. 2 compares NoPE with the period-targeting variants, while Fig. 2 reports the conventional non-periodic controls. In both variants, RoPE is applied on all dimensions. NoPE Language

∈ Class

Acc.

N∗

( aa)∗ ( ab)∗

LTL[P, MOD] LTL[P, MOD]

0.50 0.96

41 96

RoPEP

SiPEP

Acc.

N∗

Acc.

N∗

1.00 1.00

500 500

0.50 0.50

41 44

Table 2: Periodic-construction experiments. Maximum accuracy and longest perfect length over the run grid achieved by different transformer variants. 7

Published as a conference paper at COLM 2026

( ab)∗

Base

2

10 1

10 8

10 4

1

4

10 −

10 1

10 −

8

RoPEP (best run)

0 10 −

25

0

12

25

10 −

NoPE (best run)

2

50

10 8

50

10 4

SiPENP

1

RoPENP

75

4

100

75

8

100

10 −

500

12

500

10 −

Mean N ∗

( aa)∗

Base

Figure 2: Mean longest perfect length N ∗ for conventional non-periodic encodings on the modular languages. Markers are means over the run grid and whiskers are ±1 standard deviation. The two reference lines are best-run values for NoPE and RoPEP on these tasks. Neither non-periodic encoding generalizes perfectly at any tested base. RoPEP generalizes perfectly on LTL[P, MOD]. The period-targeting RoPEP model achieves accuracy 1.00 and N ∗ = 500 on both ( ab)∗ and ( aa)∗ , matching the modular-predicate construction. SiPEP struggles on LTL[P, MOD]. Although SiPEP has the same existential expressivity, the trained model does not learn either modular language. The theorem guarantees a parameterization, not that optimization will find it; one possible explanation is that absolute sinusoidal features in the residual stream are more easily overwritten. Conventional rotations do not learn the constructed modular behavior. Neither RoPENP nor SiPENP generalizes perfectly on the two periodic languages. The full sweep in Fig. 2 reaches the same conclusion at every tested base across twenty-four orders of magnitude, separating the engineered periodic behavior from conventional frequencies.

4

A Practical Account of Non-Periodic RoPE

We now analyze RoPE’s role implementing fixed-offset heads (Barbero et al., 2025a)— referencing positions at a specific displacement from the query position. This account applies naturally to conventional RoPENP , but does not capture its asymptotic behavior. Rather, it relies on a finite-precision range over which RoPE can create a reliable fixed-offset head, partly explaining its empirical advantage over SiPENP (Su et al., 2023). The proof for the bounded non-periodic RoPE simulations is in §D. 4.1

Conventional RoPE Is Non-Periodic

We first pinpoint why conventional RoPE is non-periodic. Namely, irrational rotations, those that conventional RoPE leverages, imply non-periodicity. Proposition 4.1 / Q, then i 7→
(Specialization of Walters 1982, Thm 1.8). If g/ (2π ) ∈ roundF Rotg,i is non-periodic. Hence, conventional RoPE, which contains g = 1, is non-periodic under output-rounded ideal-phase evaluation. 4.2

Fixed-Offset Attention up to a Length Bound

We now proceed to show that with irrational rotations, RoPENP transformers can implement fixed-offset attention heads. Fix an offset k ≥ 1. With exact arithmetic, a frequency g/ (2π ) ∈ / Q yields a k-offset head whose score is g,C,k Si,j = C cos ( g (i − k − j)) , 0 ≤ j < i, (9) 8

Published as a conference paper at COLM 2026

for some C > 0 (Barbero et al., 2025a). At positions i ≥ k + 1, the target j = i − k uniquely maximizes Eq. (9) with score C. For the uniqueness to hold under finite precision, the target must remain ahead by at least f large after rounding in the score computation. We define the k-offset head’s certified range as the maximum length at which it scores its target position at least f large more than any non-target position: n o def g,C,k,F g,C,k,F (k) k+1≤i ≤ L+1, Nmax ( g, C, F) = sup L ∈ N : Sbi,i−k − Sbi,j ≥ f large for 0all . (10) ≤ j<i, j̸=i −k Under exact evaluation of Eq. (9) through length L ≥ k, the sufficient gap is CδL ( g), where (k)

def

δL ( g) = 1 − max1≤n≤ L cos ( gn). Thus CδL ( g) ≥ f large certifies Nmax ( g, C, F) ≥ L. 4.3

From Fixed-Offset Heads to Yk

If the certified range is L, stable softmax makes position i − k’s weight exactly 1 for every query position i ∈ {k + 1, . . . L + 1}. Unrotated dimensions independently simulate LTL[P] and provide the boundary test for the first k positions. Corollary 4.1. Fix g, C, and F, and let L ∈ N. Write SMAT[RoPENP ]-transformers for softattention RoPENP transformers with unrotated subspaces, and let L-simulation be as in Def. D.1. (k)

(i) For every offset k ≥ 1 with k ≤ L ≤ Nmax ( g, C, F), such a transformer L-simulates the fixed-offset operator Yk . (1)

(ii) If 1 ≤ L ≤ Nmax ( g, C, F), it L-simulates every LTL[P, Y]-definable formula. More gen(k)

erally, for a finite set of offsets K ⊆ N≥1 with max K ≤ L ≤ mink∈K Nmax ( g, C, F), it L-simulates every formula built from atomic predicates, Boolean connectives, P, and the operators {Yk : k ∈ K }. (iii) Moreover, for every L ∈ N and every finite offset set K there exist a rotation angle g with g/ (2π ) ∈ / Q, scales C, and a finite-precision regime F satisfying the hypothesis of (ii). The connection to LTL[P, Y] links the result to the extra power of local attention (Li & Cotterell, 2026) and resembles the finite-precision implementation of n-gram heads (Svete & Cotterell, 2024; Svete et al., 2024). 4.4

Testing the Locality Account

We evaluate whether the bounded fixed-offset mechanism appears in length generalization, under the protocol of §3.5. RoPE is again applied on all dimensions.

Base

Base

8

4

10 −

10 −

12

125 100 75 50 25 0 10 −

10 8 10 1 2

4

1 10 4

8

10 −

12

2

10 8 10 1

4

1 10 4

8

10 −

12

10 −

40

10 −

80

500 400 300 200 100 0 10 −

120

10 −

Mean N ∗

160

0

Σ∗ abΣ∗ ∈ LTL[P, Y]

aΣ∗ ∈ LTL[P]

10 8 10 1 2

Σ∗ a ∈ LTL[Y]

NoPE ± 1 std

NoPE mean

1 10 4

RoPENP (mean ± 1 std)

Base

Figure 3: Mean longest perfect length N ∗ . Whiskers are ±1 standard deviation over the run grid and the grey band is the corresponding NoPE interval. 9

Published as a conference paper at COLM 2026

The standard base is not uniformly best. On each single-operator language, the conventional base β = 104 gives the lowest mean N ∗ among the seven tested bases: 45.5 on Σ∗ a and 146.9 on aΣ∗ . Every tested base on either side of 104 improves on these two values. This mirrors the extrapolation experiments of Liu et al. (2024), who find 104 to be the worst tested base after fine-tuning and report improvements from both smaller and larger bases. The pattern is not universal, as, on the combined P–Y language, 101 2 performs worse. This suggests that the optimal base is task-dependent. RoPENP improves on a Y language. On Σ∗ a, RoPENP ’s mean N ∗ exceeds NoPE’s at six of seven bases (Fig. 3). The certified-range result offers a mechanism: Relative scores can isolate the preceding position while their finite-precision gap remains large enough. As length grows, more competing offsets appear, increasing the chance of a numerical collision and making the behavior brittle. RoPENP can disrupt P reasoning. On aΣ∗ , the NoPE mean is 470.5, whereas the RoPENP means range from 146.9 to 402.9. On Σ∗ abΣ∗ , the NoPE mean is 92.9, whereas the RoPENP means range from 46.1 to 61.9. This suggests a tradeoff: Relative displacement can help retrieve a nearby symbol while disrupting the nearly position-invariant aggregation that supports conditioning on distant information. Conventional RoPE therefore behaves more like a bounded source of Y access than a monotonic expressivity improvement over NoPE. We conjecture that partial-RoPE (Barbero et al., 2025a; Khan et al., 2026) and NoPE-RoPE hybrid attention (Yang et al., 2025c) variants should empirically improve on long-context P reasoning while retaining the locality bias of RoPENP .

5

Discussion

Two regimes. For component-periodic schedules, RoPEP yields precisely LTL[P, MOD] over arbitrary input lengths, enabling modular reasoning over input positions. The conventional RoPENP behaves qualitatively differently: Relative scores can directly identify any fixed offset k, but only while finite precision preserves a sufficient score gap, yielding bounded Yk operators and a bounded simulation of LTL[P, Y]. The two accounts therefore differ both in their schedule assumption and in whether the claim is uniform over all lengths. With unrotated subspaces, RoPE also retains the P reasoning of NoPE—checking whether a symbol occurs anywhere in the context. Limitations. Our periodic lower bound uses a repeated finite table and a tailored exact value set, and does not imply that standard frequencies or optimization discover modular behavior. Empirical results, however, suggest that strong modular behavior often appears. The locality result of §4 is bounded and is not an all-length characterization of RoPENP . Architectural implications. The comparison suggests reserving unrotated dimensions when a model must combine global P reasoning with periodic or local relative-position information. It also supports treating rotation structure as an explicit architectural choice, consistent with work questioning broad long-context claims for RoPE (Du et al., 2026). Neither account gives RoPE general state-tracking or regular language recognition abilities (Liu et al., 2023b), such as those required by Flip-Flop language modeling (Liu et al., 2023a). Alternative state-tracking mechanisms include rational transductors (Mohri, 2026) and transformer–linear-RNN hybrids (Merrill et al., 2026b;a). A remaining theoretical question is how the known depth hierarchy for RoPE transformers (Yang et al., 2025b) differs between exact periodic and bounded-local regimes.

Acknowledgments We are grateful to William Merrill and Andy Yang for valuable comments on this work. Selim Jerad thanks Makoto Yamada and the MLDS Unit at the Okinawa Institute of Science and Technology for hosting him while writing this paper. Anej Svete and Jiaoda Li are 10

Published as a conference paper at COLM 2026

supported by an ETH AI Center Doctoral Fellowship. We used generative AI to improve our writing. Every modification introduced by generative AI was carefully reviewed by the authors, who take full responsibility for it.

References Jorge Almeida. Pseudovarieties of semigroups. Asian-European Journal of Mathematics, May 2025. ISSN 1793-7183. doi: 10.1142/s1793557125400078. URL http://dx.doi.org/10. 1142/S1793557125400078. Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, Binyuan Hui, Luo Ji, Mei Li, Junyang Lin, Runji Lin, Dayiheng Liu, Gao Liu, Chengqiang Lu, Keming Lu, Jianxin Ma, Rui Men, Xingzhang Ren, Xuancheng Ren, Chuanqi Tan, Sinan Tan, Jianhong Tu, Peng Wang, Shijie Wang, Wei Wang, Shengguang Wu, Benfeng Xu, Jin Xu, An Yang, Hao Yang, Jian Yang, Shusheng Yang, Yang Yao, Bowen Yu, Hongyi Yuan, Zheng Yuan, Jianwei Zhang, Xingxuan Zhang, Yichang Zhang, Zhenru Zhang, Chang Zhou, Jingren Zhou, Xiaohuan Zhou, and Tianhang Zhu. Qwen technical report, 2023. URL https://arxiv.org/abs/2309.16609. Federico Barbero, Alex Vitvitskyi, Christos Perivolaropoulos, Razvan Pascanu, and Petar Veličković. Round and round we go! what makes rotary positional encodings useful?, 2025a. URL https://arxiv.org/abs/2410.06205. Federico Barbero, Álvaro Arroyo, Xiangming Gu, Christos Perivolaropoulos, Michael Bronstein, Petar Veličković, and Razvan Pascanu. Why do llms attend to the first token?, 2025b. URL https://arxiv.org/abs/2504.02732. Janusz Antoni Brzozowski and Faith Ellen. Languages of R-trivial monoids. Journal of Computer and System Sciences, 20(1):32–49, 1980. ISSN 0022-0000. doi: https://doi.org/ 10.1016/0022-0000(80)90003-3. URL https://www.sciencedirect.com/science/article/ pii/0022000080900033. David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders, 2023. URL https://arxiv.org/abs/2301.10743. Luc Dartois and Charles Paperman. Two-variable first order logic with modular predicates over words. In Natacha Portier and Thomas Wilke (eds.), 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 329–340, Dagstuhl, Germany, 2013. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-939897-50-7. doi: 10.4230/LIPIcs.STACS. 2013.329. URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS. 2013.329. Luc Dartois and Charles Paperman. Adding modular predicates to first-order fragments, 2015. URL https://arxiv.org/abs/1401.6576. DeepSeek-AI, Anyi Xu, Bangcai Lin, Bing Xue, Bingxuan Wang, Bingzheng Xu, Bochao Wu, Bowei Zhang, Chaofan Lin, Chen Dong, Chenchen Ling, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chengyu Hou, Chenhao Xu, Chenze Shao, Chong Ruan, Conner Sun, Damai Dai, Daya Guo, Dejian Yang, Deli Chen, Donghao Li, Dongjie Ji, Erhang Li, Fang Wei, Fangyun Lin, Fangzhou Yuan, Feiyu Xia, Fucong Dai, Guangbo Hao, Guanting Chen, Guoai Cao, Guolai Meng, Guowei Li, Han Yu, Han Zhang, Hanwei Xu, Hao Li, Haofen Liang, Haoling Zhang, Haoming Luo, Haoran Wei, Haotian Yuan, Haowei Zhang, Haowen Luo, Haoyu Chen, Haozhe Ji, Hengqing Zhang, Honghui Ding, Hongxuan Tang, Huanqi Cao, Huazuo Gao, Hui Qu, Hui Zeng, J Yang, JQ Zhu, Jia Luo, Jia Song, Jia Yu, Jialiang Huang, Jialu Cai, Jian Liang, Jiangting Zhou, Jiasheng Ye, Jiashi Li, Jiaxin Xu, Jiewen Hu, Jieyu Yang, Jin Chen, Jin Yan, Jingchang Chen, Jingli Zhou, Jingting Xiang, Jingyang Yuan, Jingyuan Cheng, Jingzi Zhou, Jinhua Zhu, Jiping Yu, Joseph Sun, Jun Ran, Junguang Jiang, Junjie Qiu, Junlong Li, Junmin Zheng, Junxiao Song, Kai Dong, Kaige Gao, Kang Guan, Kexing Zhou, Kezhao Huang, Kuai Yu, Lean Wang, Lecong Zhang, Lei Wang, Leyi Xia, Li Zhang, Liang Zhao, Lihua Guo, Lingxiao Luo, Linwang 11

Published as a conference paper at COLM 2026

Ma, Linyan Zhu, Litong Wang, Liyu Cai, Liyue Zhang, Longhao Chen, MS Di, MY Xu, Max Mei, Miaojun Wang, Mingchuan Zhang, Minghua Zhang, Minghui Tang, Mingming Li, Mingxu Zhou, Minmin Han, Ning Wang, Panpan Huang, Panpan Wang, Peixin Cong, Peiyi Wang, Peng Zhang, Qiancheng Wang, Qihao Zhu, Qingyang Li, Qinyu Chen, Qiushi Du, Qiwei Jiang, Rui Tian, Ruifan Xu, Ruijie Lu, Ruiling Xu, Ruiqi Ge, Ruisong Zhang, Ruizhe Pan, Runji Wang, Runqian Chen, Runqiu Yin, Runxin Xu, Ruomeng Shen, Ruoyu Zhang, Ruyi Chen, SH Liu, Shanghao Lu, Shangmian Sun, Shangyan Zhou, Shanhuang Chen, Shaofei Cai, Shaoheng Nie, Shaoqing Wu, Shaoyuan Chen, Shengding Hu, Shengyu Liu, Shiqiang Hu, Shirong Ma, Shiyu Wang, Shuiping Yu, Shunfeng Zhou, Shuting Pan, Shuying Yu, Songyang Zhou, Tao Ni, Tao Yun, Tian Jin, Tian Pei, Tian Ye, Tianle Lin, Tianran Ji, Tianyi Cui, Tianyuan Yue, Tingting Yu, Tun Wang, W Zhang, WL Xiao, Wangding Zeng, Wei An, Weilin Zhao, Wen Liu, Wenfeng Liang, Wenjie Pang, Wenjing Luo, Wenjing Yao, Wenjun Gao, Wenkai Yang, Wenlve Huang, Wenqing Hou, Wentao Zhang, Wenting Ma, Xi Gao, Xiang He, Xiangwen Wang, Xianzu Wang, Xiao Bi, Xiaodong Liu, Xiaohan Wang, Xiaokang Chen, Xiaokang Zhang, Xiaotao Nie, Xiaowen Sun, Xiaoxiang Wang, Xin Cheng, Xin Liu, Xin Xie, Xingchao Liu, Xingchen Liu, Xingkai Yu, Xingyou Li, Xinyu Yang, Xinyu Zhang, Xu Chen, Xuanyu Wang, Xuecheng Su, Xueyin Chen, Xuheng Lin, Xuwei Fu, YC Yan, YQ Wang, YW Ma, Yanfeng Luo, Yang Zhang, Yanhong Xu, Yanru Ma, Yanwen Huang, Yao Li, Yao Li, Yao Xu, Yao Zhao, Yaofeng Sun, Yaohui Wang, Yi Qian, Yi Shao, Yi Yu, Yichao Zhang, Yifan Ding, Yifan Shi, Yijia Wu, Yiliang Xiong, Yiling Ma, Ying He, Ying Tang, Ying Zhou, Yingjia Luo, Yinmin Zhong, Yishi Piao, Yisong Wang, Yixiang Zhang, Yixiao Chen, Yixuan Tan, Yixuan Wei, Yiyang Ma, Yiyuan Liu, Yonglun Yang, Yongqiang Guo, Yongtong Wu, Yu Wu, YuKun Li, Yuan Cheng, Yuan Ou, Yuanfan Xu, Yuanhao Li, Yuduan Wang, Yuehan Yang, Yuer Xu, Yuhan Wu, Yuhao Meng, Yuheng Zou, Yukun Zha, Yunfan Xiong, Yupeng Chen, Yuping Lin, Yuqian Cao, Yuqian Wang, Yushun Zhang, Yuting Yan, Yutong Lin, Yuxian Gu, Yuxiang Luo, Yuxiang You, Yuxuan Liu, Yuxuan Zhou, Yuyang Zhou, Yuzhen Huang, ZF Wu, Zehao Wang, Zehua Zhao, Zehui Ren, Zekai Zhang, Zhangli Sha, Zhe Fu, Zhe Ju, Zhean Xu, Zhenda Xie, Zhengyan Zhang, Zheren Gao, Zhewen Hao, Zhibin Gou, Zhicheng Ma, Zhigang Yan, Zhihong Shao, Zhixian Huang, Zhixuan Chen, Zhiyu Wu, Zhizhou Ren, Zhongyu Wu, Zhuoshu Li, Zhuping Zhang, Zian Xu, Zihao Wang, Zihua Qu, Zihui Gu, Zijia Zhu, Zilin Li, Zipeng Zhang, Ziwei Xie, Ziyi Gao, Ziyi Wan, Zizheng Pan, and Zongqing Yao. Deepseek-v4: Towards highly efficient million-token context intelligence, 2026. URL https://arxiv.org/abs/2606.19348. Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. Neural networks and the chomsky hierarchy, 2023. URL https://arxiv.org/abs/2207.02098. Yufeng Du, Phillip Harris, Minyang Tian, Eliu A Huerta, Srikanth Ronanki, Subendhu Rongali, Aram Galstyan, and Hao Peng. Rope distinguishes neither positions nor tokens in long contexts, provably, 2026. URL https://arxiv.org/abs/2605.15514. Dov Gabbay, Amir Pnueli, Saharon Shelah, and Jonathan Stavi. On the temporal analysis of fairness. In Proceedings of the 7th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’80, pp. 163–173, New York, NY, USA, 1980. Association for Computing Machinery. ISBN 0897910117. doi: 10.1145/567446.567462. URL https: //doi.org/10.1145/567446.567462. Yoav Gelberg, Koshi Eguchi, Takuya Akiba, and Edoardo Cetin. Extending the context of pretrained llms by dropping their positional embeddings, 2025. URL https://arxiv.org/ abs/2512.12167. Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, Arun Rao, Aston Zhang, Aurelien Rodriguez, Austen Gregerson, Ava Spataru, Baptiste Roziere, Bethany Biron, Binh Tang, Bobbie Chern, Charlotte Caucheteux, Chaya Nayak, Chloe Bi, Chris Marra, Chris McConnell, Christian Keller, Christophe Touret, Chunyang Wu, Corinne Wong, Cristian Canton Ferrer, 12

Published as a conference paper at COLM 2026

Cyrus Nikolaidis, Damien Allonsius, Daniel Song, Danielle Pintz, Danny Livshits, Danny Wyatt, David Esiobu, Dhruv Choudhary, Dhruv Mahajan, Diego Garcia-Olano, Diego Perino, Dieuwke Hupkes, Egor Lakomkin, Ehab AlBadawy, Elina Lobanova, Emily Dinan, Eric Michael Smith, Filip Radenovic, Francisco Guzmán, Frank Zhang, Gabriel Synnaeve, Gabrielle Lee, Georgia Lewis Anderson, Govind Thattai, Graeme Nail, Gregoire Mialon, Guan Pang, Guillem Cucurell, Hailey Nguyen, Hannah Korevaar, Hu Xu, Hugo Touvron, Iliyan Zarov, Imanol Arrieta Ibarra, Isabel Kloumann, Ishan Misra, Ivan Evtimov, Jack Zhang, Jade Copet, Jaewon Lee, Jan Geffert, Jana Vranes, Jason Park, Jay Mahadeokar, Jeet Shah, Jelmer van der Linde, Jennifer Billock, Jenny Hong, Jenya Lee, Jeremy Fu, Jianfeng Chi, Jianyu Huang, Jiawen Liu, Jie Wang, Jiecao Yu, Joanna Bitton, Joe Spisak, Jongsoo Park, Joseph Rocca, Joshua Johnstun, Joshua Saxe, Junteng Jia, Kalyan Vasuden Alwala, Karthik Prasad, Kartikeya Upasani, Kate Plawiak, Ke Li, Kenneth Heafield, Kevin Stone, Khalid El-Arini, Krithika Iyer, Kshitiz Malik, Kuenley Chiu, Kunal Bhalla, Kushal Lakhotia, Lauren Rantala-Yeary, Laurens van der Maaten, Lawrence Chen, Liang Tan, Liz Jenkins, Louis Martin, Lovish Madaan, Lubo Malo, Lukas Blecher, Lukas Landzaat, Luke de Oliveira, Madeline Muzzi, Mahesh Pasupuleti, Mannat Singh, Manohar Paluri, Marcin Kardas, Maria Tsimpoukelli, Mathew Oldham, Mathieu Rita, Maya Pavlova, Melanie Kambadur, Mike Lewis, Min Si, Mitesh Kumar Singh, Mona Hassan, Naman Goyal, Narjes Torabi, Nikolay Bashlykov, Nikolay Bogoychev, Niladri Chatterji, Ning Zhang, Olivier Duchenne, Onur Çelebi, Patrick Alrassy, Pengchuan Zhang, Pengwei Li, Petar Vasic, Peter Weng, Prajjwal Bhargava, Pratik Dubal, Praveen Krishnan, Punit Singh Koura, Puxin Xu, Qing He, Qingxiao Dong, Ragavan Srinivasan, Raj Ganapathy, Ramon Calderer, Ricardo Silveira Cabral, Robert Stojnic, Roberta Raileanu, Rohan Maheswari, Rohit Girdhar, Rohit Patel, Romain Sauvestre, Ronnie Polidoro, Roshan Sumbaly, Ross Taylor, Ruan Silva, Rui Hou, Rui Wang, Saghar Hosseini, Sahana Chennabasappa, Sanjay Singh, Sean Bell, Seohyun Sonia Kim, Sergey Edunov, Shaoliang Nie, Sharan Narang, Sharath Raparthy, Sheng Shen, Shengye Wan, Shruti Bhosale, Shun Zhang, Simon Vandenhende, Soumya Batra, Spencer Whitman, Sten Sootla, Stephane Collot, Suchin Gururangan, Sydney Borodinsky, Tamar Herman, Tara Fowler, Tarek Sheasha, Thomas Georgiou, Thomas Scialom, Tobias Speckbacher, Todor Mihaylov, Tong Xiao, Ujjwal Karn, Vedanuj Goswami, Vibhor Gupta, Vignesh Ramanathan, Viktor Kerkez, Vincent Gonguet, Virginie Do, Vish Vogeti, Vítor Albiero, Vladan Petrovic, Weiwei Chu, Wenhan Xiong, Wenyin Fu, Whitney Meers, Xavier Martinet, Xiaodong Wang, Xiaofang Wang, Xiaoqing Ellen Tan, Xide Xia, Xinfeng Xie, Xuchao Jia, Xuewei Wang, Yaelle Goldschlag, Yashesh Gaur, Yasmine Babaei, Yi Wen, Yiwen Song, Yuchen Zhang, Yue Li, Yuning Mao, Zacharie Delpierre Coudert, Zheng Yan, Zhengxing Chen, Zoe Papakipos, Aaditya Singh, Aayushi Srivastava, Abha Jain, Adam Kelsey, Adam Shajnfeld, Adithya Gangidi, Adolfo Victoria, Ahuva Goldstand, Ajay Menon, Ajay Sharma, Alex Boesenberg, Alexei Baevski, Allie Feinstein, Amanda Kallet, Amit Sangani, Amos Teo, Anam Yunus, Andrei Lupu, Andres Alvarado, Andrew Caples, Andrew Gu, Andrew Ho, Andrew Poulton, Andrew Ryan, Ankit Ramchandani, Annie Dong, Annie Franco, Anuj Goyal, Aparajita Saraf, Arkabandhu Chowdhury, Ashley Gabriel, Ashwin Bharambe, Assaf Eisenman, Azadeh Yazdan, Beau James, Ben Maurer, Benjamin Leonhardi, Bernie Huang, Beth Loyd, Beto De Paola, Bhargavi Paranjape, Bing Liu, Bo Wu, Boyu Ni, Braden Hancock, Bram Wasti, Brandon Spence, Brani Stojkovic, Brian Gamido, Britt Montalvo, Carl Parker, Carly Burton, Catalina Mejia, Ce Liu, Changhan Wang, Changkyu Kim, Chao Zhou, Chester Hu, Ching-Hsiang Chu, Chris Cai, Chris Tindal, Christoph Feichtenhofer, Cynthia Gao, Damon Civin, Dana Beaty, Daniel Kreymer, Daniel Li, David Adkins, David Xu, Davide Testuggine, Delia David, Devi Parikh, Diana Liskovich, Didem Foss, Dingkang Wang, Duc Le, Dustin Holland, Edward Dowling, Eissa Jamil, Elaine Montgomery, Eleonora Presani, Emily Hahn, Emily Wood, Eric-Tuan Le, Erik Brinkman, Esteban Arcaute, Evan Dunbar, Evan Smothers, Fei Sun, Felix Kreuk, Feng Tian, Filippos Kokkinos, Firat Ozgenel, Francesco Caggioni, Frank Kanayet, Frank Seide, Gabriela Medina Florez, Gabriella Schwarz, Gada Badeer, Georgia Swee, Gil Halpern, Grant Herman, Grigory Sizov, Guangyi, Zhang, Guna Lakshminarayanan, Hakan Inan, Hamid Shojanazeri, Han Zou, Hannah Wang, Hanwen Zha, Haroun Habeeb, Harrison Rudolph, Helen Suk, Henry Aspegren, Hunter Goldman, Hongyuan Zhan, Ibrahim Damlaj, Igor Molybog, Igor Tufanov, Ilias Leontiadis, Irina-Elena Veliche, Itai Gat, Jake Weissman, James Geboski, James Kohli, Janice Lam, Japhet Asher, Jean-Baptiste Gaya, Jeff Marcus, Jeff Tang, Jennifer Chan, Jenny Zhen, Jeremy Reizenstein, Jeremy Teboul, 13

Published as a conference paper at COLM 2026

Jessica Zhong, Jian Jin, Jingyi Yang, Joe Cummings, Jon Carvill, Jon Shepard, Jonathan McPhie, Jonathan Torres, Josh Ginsburg, Junjie Wang, Kai Wu, Kam Hou U, Karan Saxena, Kartikay Khandelwal, Katayoun Zand, Kathy Matosich, Kaushik Veeraraghavan, Kelly Michelena, Keqian Li, Kiran Jagadeesh, Kun Huang, Kunal Chawla, Kyle Huang, Lailin Chen, Lakshya Garg, Lavender A, Leandro Silva, Lee Bell, Lei Zhang, Liangpeng Guo, Licheng Yu, Liron Moshkovich, Luca Wehrstedt, Madian Khabsa, Manav Avalani, Manish Bhatt, Martynas Mankus, Matan Hasson, Matthew Lennie, Matthias Reso, Maxim Groshev, Maxim Naumov, Maya Lathi, Meghan Keneally, Miao Liu, Michael L. Seltzer, Michal Valko, Michelle Restrepo, Mihir Patel, Mik Vyatskov, Mikayel Samvelyan, Mike Clark, Mike Macey, Mike Wang, Miquel Jubert Hermoso, Mo Metanat, Mohammad Rastegari, Munish Bansal, Nandhini Santhanam, Natascha Parks, Natasha White, Navyata Bawa, Nayan Singhal, Nick Egebo, Nicolas Usunier, Nikhil Mehta, Nikolay Pavlovich Laptev, Ning Dong, Norman Cheng, Oleg Chernoguz, Olivia Hart, Omkar Salpekar, Ozlem Kalinli, Parkin Kent, Parth Parekh, Paul Saab, Pavan Balaji, Pedro Rittner, Philip Bontrager, Pierre Roux, Piotr Dollar, Polina Zvyagina, Prashant Ratanchandani, Pritish Yuvraj, Qian Liang, Rachad Alao, Rachel Rodriguez, Rafi Ayub, Raghotham Murthy, Raghu Nayani, Rahul Mitra, Rangaprabhu Parthasarathy, Raymond Li, Rebekkah Hogan, Robin Battey, Rocky Wang, Russ Howes, Ruty Rinott, Sachin Mehta, Sachin Siby, Sai Jayesh Bondu, Samyak Datta, Sara Chugh, Sara Hunt, Sargun Dhillon, Sasha Sidorov, Satadru Pan, Saurabh Mahajan, Saurabh Verma, Seiji Yamamoto, Sharadh Ramaswamy, Shaun Lindsay, Shaun Lindsay, Sheng Feng, Shenghao Lin, Shengxin Cindy Zha, Shishir Patil, Shiva Shankar, Shuqiang Zhang, Shuqiang Zhang, Sinong Wang, Sneha Agarwal, Soji Sajuyigbe, Soumith Chintala, Stephanie Max, Stephen Chen, Steve Kehoe, Steve Satterfield, Sudarshan Govindaprasad, Sumit Gupta, Summer Deng, Sungmin Cho, Sunny Virk, Suraj Subramanian, Sy Choudhury, Sydney Goldman, Tal Remez, Tamar Glaser, Tamara Best, Thilo Koehler, Thomas Robinson, Tianhe Li, Tianjun Zhang, Tim Matthews, Timothy Chou, Tzook Shaked, Varun Vontimitta, Victoria Ajayi, Victoria Montanez, Vijai Mohan, Vinay Satish Kumar, Vishal Mangla, Vlad Ionescu, Vlad Poenaru, Vlad Tiberiu Mihailescu, Vladimir Ivanov, Wei Li, Wenchen Wang, Wenwen Jiang, Wes Bouaziz, Will Constable, Xiaocheng Tang, Xiaojian Wu, Xiaolan Wang, Xilun Wu, Xinbo Gao, Yaniv Kleinman, Yanjun Chen, Ye Hu, Ye Jia, Ye Qi, Yenda Li, Yilin Zhang, Ying Zhang, Yossi Adi, Youngjin Nam, Yu, Wang, Yu Zhao, Yuchen Hao, Yundi Qian, Yunlu Li, Yuzi He, Zach Rait, Zachary DeVito, Zef Rosnbrick, Zhaoduo Wen, Zhenyu Yang, Zhiwei Zhao, and Zhiyu Ma. The llama 3 herd of models, 2024. URL https://arxiv.org/abs/2407.21783. Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10:800–810, 2022. doi: 10.1162/tacl_a_00490. URL https: //aclanthology.org/2022.tacl-1.46/. Simin Huo. Periodic rope for infinite context llms, 2026. URL https://arxiv.org/abs/2605. 27980. Selim Jerad, Anej Svete, Jiaoda Li, and Ryan Cotterell. Unique hard attention: A tale of two sides. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 977–996, Vienna, Austria, July 2025. Association for Computational Linguistics. ISBN 979-8-89176-252-7. doi: 10.18653/v1/2025.acl-short.76. URL https://aclanthology.org/2025.acl-short.76/. Hans Kamp. Tense Logic and the Theory of Linear Order. PhD thesis, UCLA, 1968. URL https://www.proquest.com/openview/408039eb4ed228dc4cba3fe7e1774163/ 1?pq-origsite=gscholar&cbl=18750&diss=y. Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in transformers, 2023. URL https://arxiv.org/abs/2305.19466. Mohammad Aflah Khan, Krishna P. Gummadi, Manish Gupta, and Abhilasha Ravichander. Fractional rotation, full potential? investigating performance and convergence of partial rope, 2026. URL https://arxiv.org/abs/2603.11611. 14

Published as a conference paper at COLM 2026

Jiaoda Li and Ryan Cotterell. Characterizing the expressivity of fixed-precision transformer language models, 2025. URL https://arxiv.org/abs/2505.23623. Jiaoda Li and Ryan Cotterell. Characterizing the expressivity of local attention in transformers, 2026. URL https://arxiv.org/abs/2605.00768. Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Exposing attention glitches with flip-flop language modeling, 2023a. URL https://arxiv.org/abs/ 2306.00946. Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Representations, 2023b. URL https://openreview.net/forum?id=De4FYqjFueZ. Xiaoran Liu, Hang Yan, Shuo Zhang, Chenxin An, Xipeng Qiu, and Dahua Lin. Scaling laws of rope-based extrapolation, 2024. URL https://arxiv.org/abs/2310.05209. Robert McNaughton and Seymour Papert. Counter-Free Automata. M.I.T. Press research monographs. M.I.T. Press, 1971. ISBN 9780262130769. URL https://mitpress.mit.edu/ 9780262130769/counter-free-automata/. Xin Men, Mingyu Xu, Bingning Wang, Qingyu Zhang, Hongyu Lin, Xianpei Han, and Weipeng Chen. Base of rope bounds context length, 2024. URL https://arxiv.org/abs/ 2405.14591. William Merrill, Hongjian Jiang, Yanhong Li, Anthony Lin, and Ashish Sabharwal. Why are linear rnns more parallelizable?, 2026a. URL https://arxiv.org/abs/2603.03612. William Merrill, Yanhong Li, Tyler Romero, Anej Svete, Caia Costello, Pradeep Dasigi, Dirk Groeneveld, David Heineman, Bailey Kuehl, Nathan Lambert, Chuan Li, Kyle Lo, Saumya Malik, DJ Matusz, Benjamin Minixhofer, Jacob Morrison, Luca Soldaini, Finbarr Timbers, Pete Walsh, Noah A. Smith, Hannaneh Hajishirzi, and Ashish Sabharwal. Olmo hybrid: From theory to practice and back, 2026b. URL https://arxiv.org/abs/2604.03444. Mehryar Mohri. Rational transductors, 2026. URL https://arxiv.org/abs/2602.07599. Masato Neishi and Naoki Yoshinaga. On the relation between position information and sentence length in neural machine translation. In Mohit Bansal and Aline Villavicencio (eds.), Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL), pp. 328–338, Hong Kong, China, November 2019. Association for Computational Linguistics. doi: 10.18653/v1/K19-1031. URL https://aclanthology.org/K19-1031/. Team Olmo, :, Allyson Ettinger, Amanda Bertsch, Bailey Kuehl, David Graham, David Heineman, Dirk Groeneveld, Faeze Brahman, Finbarr Timbers, Hamish Ivison, Jacob Morrison, Jake Poznanski, Kyle Lo, Luca Soldaini, Matt Jordan, Mayee Chen, Michael Noukhovitch, Nathan Lambert, Pete Walsh, Pradeep Dasigi, Robert Berry, Saumya Malik, Saurabh Shah, Scott Geng, Shane Arora, Shashank Gupta, Taira Anderson, Teng Xiao, Tyler Murray, Tyler Romero, Victoria Graf, Akari Asai, Akshita Bhagia, Alexander Wettig, Alisa Liu, Aman Rangapur, Chloe Anastasiades, Costa Huang, Dustin Schwenk, Harsh Trivedi, Ian Magnusson, Jaron Lochner, Jiacheng Liu, Lester James V. Miranda, Maarten Sap, Malia Morgan, Michael Schmitz, Michal Guerquin, Michael Wilson, Regan Huff, Ronan Le Bras, Rui Xin, Rulin Shao, Sam Skjonsberg, Shannon Zejiang Shen, Shuyue Stella Li, Tucker Wilde, Valentina Pyatkin, Will Merrill, Yapei Chang, Yuling Gu, Zhiyuan Zeng, Ashish Sabharwal, Luke Zettlemoyer, Pang Wei Koh, Ali Farhadi, Noah A. Smith, and Hannaneh Hajishirzi. Olmo 3, 2025. URL https://arxiv.org/abs/2512.13961. Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=R8sQPpGCv0. Jan Rosendahl, Viet Anh Khoa Tran, Weiyue Wang, and Hermann Ney. Analysis of positional encodings for neural machine translation. In Jan Niehues, Rolando Cattoni, Sebastian Stüker, Matteo Negri, Marco Turchi, Thanh-Le Ha, Elizabeth Salesky, Ramon Sanabria, 15

Published as a conference paper at COLM 2026

Loic Barrault, Lucia Specia, and Marcello Federico (eds.), Proceedings of the 16th International Conference on Spoken Language Translation, Hong Kong, November 2-3 2019. Association for Computational Linguistics. URL https://aclanthology.org/2019.iwslt-1.20/. Jianlin Su, Yu Lu, Shengfeng Pan, Ahmed Murtadha, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding, 2023. URL https://arxiv.org/ abs/2104.09864. Anej Svete and Ryan Cotterell. Transformers can represent n-gram language models. In Kevin Duh, Helena Gomez, and Steven Bethard (eds.), Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pp. 6845–6881, Mexico City, Mexico, June 2024. Association for Computational Linguistics. doi: 10.18653/v1/2024.naacl-long.381. URL https://aclanthology.org/2024.naacl-long.381/. Anej Svete, Nadav Borenstein, Mike Zhou, Isabelle Augenstein, and Ryan Cotterell. Can transformers learn n-gram language models? In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 9851–9867, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: 10.18653/v1/2024.emnlp-main.550. URL https: //aclanthology.org/2024.emnlp-main.550/. Anej Svete, William Merrill, Ryan Cotterell, and Ashish Sabharwal. Revisiting padded transformer expressivity: Which architectural choices matter and which don’t. In Fortythird International Conference on Machine Learning, 2026. URL https://openreview.net/ forum?id=nBuL6HywFX. Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, Pouya Tafti, Léonard Hussenot, Pier Giuseppe Sessa, Aakanksha Chowdhery, Adam Roberts, Aditya Barua, Alex Botev, Alex Castro-Ros, Ambrose Slone, Amélie Héliou, Andrea Tacchetti, Anna Bulanova, Antonia Paterson, Beth Tsai, Bobak Shahriari, Charline Le Lan, Christopher A. Choquette-Choo, Clément Crepy, Daniel Cer, Daphne Ippolito, David Reid, Elena Buchatskaya, Eric Ni, Eric Noland, Geng Yan, George Tucker, GeorgeChristian Muraru, Grigory Rozhdestvenskiy, Henryk Michalewski, Ian Tenney, Ivan Grishchenko, Jacob Austin, James Keeling, Jane Labanowski, Jean-Baptiste Lespiau, Jeff Stanway, Jenny Brennan, Jeremy Chen, Johan Ferret, Justin Chiu, Justin Mao-Jones, Katherine Lee, Kathy Yu, Katie Millican, Lars Lowe Sjoesund, Lisa Lee, Lucas Dixon, Machel Reid, Maciej Mikuła, Mateo Wirth, Michael Sharman, Nikolai Chinaev, Nithum Thain, Olivier Bachem, Oscar Chang, Oscar Wahltinez, Paige Bailey, Paul Michel, Petko Yotov, Rahma Chaabouni, Ramona Comanescu, Reena Jana, Rohan Anil, Ross McIlroy, Ruibo Liu, Ryan Mullins, Samuel L Smith, Sebastian Borgeaud, Sertan Girgin, Sholto Douglas, Shree Pandya, Siamak Shakeri, Soham De, Ted Klimenko, Tom Hennigan, Vlad Feinberg, Wojciech Stokowiec, Yu hui Chen, Zafarali Ahmed, Zhitao Gong, Tris Warkentin, Ludovic Peran, Minh Giang, Clément Farabet, Oriol Vinyals, Jeff Dean, Koray Kavukcuoglu, Demis Hassabis, Zoubin Ghahramani, Douglas Eck, Joelle Barral, Fernando Pereira, Eli Collins, Armand Joulin, Noah Fiedel, Evan Senter, Alek Andreev, and Kathleen Kenealy. Gemma: Open models based on gemini research and technology, 2024. URL https://arxiv.org/abs/2403.08295. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, 2017. URL https://arxiv.org/abs/1706.03762. P. Walters. An Introduction to Ergodic Theory. Graduate texts in mathematics. Springer-Verlag, 1982. ISBN 9783540905998. URL https://books.google.com/books?id=GCH_wAEACAAJ. Suyuchen Wang, Ivan Kobyzev, Peng Lu, Mehdi Rezagholizadeh, and Bang Liu. Resonance RoPE: Improving context length generalization of large language models. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Findings of the Association for 16

Published as a conference paper at COLM 2026

Computational Linguistics: ACL 2024, pp. 586–598, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10.18653/v1/2024.findings-acl.32. URL https://aclanthology.org/2024.findings-acl.32/. Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks, 2024. URL https://arxiv.org/abs/2309. 17453. An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jing Zhou, Jingren Zhou, Junyang Lin, Kai Dang, Keqin Bao, Kexin Yang, Le Yu, Lianghao Deng, Mei Li, Mingfeng Xue, Mingze Li, Pei Zhang, Peng Wang, Qin Zhu, Rui Men, Ruize Gao, Shixuan Liu, Shuang Luo, Tianhao Li, Tianyi Tang, Wenbiao Yin, Xingzhang Ren, Xinyu Wang, Xinyu Zhang, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yinger Zhang, Yu Wan, Yuqiong Liu, Zekun Wang, Zeyu Cui, Zhenru Zhang, Zhipeng Zhou, and Zihan Qiu. Qwen3 technical report, 2025a. URL https://arxiv.org/abs/2505.09388. Andy Yang and David Chiang. Counting like transformers: Compiling temporal counting logic into softmax transformers. In First Conference on Language Modeling, 2024. URL https://openreview.net/forum?id=FmhPg4UJ9K. Andy Yang, David Chiang, and Dana Angluin. Masked hard-attention transformers recognize exactly the star-free languages, 2024. URL https://arxiv.org/abs/2310.13897. Andy Yang, Michaël Cadilhac, and David Chiang. Knee-deep in c-rasp: A transformer depth hierarchy, 2025b. URL https://arxiv.org/abs/2506.16055. Bowen Yang, Bharat Venkitesh, Dwaraknath Gnaneshwar Talupuru, Hangyu Lin, David Cairuz, Phil Blunsom, and Acyr Locatelli. Rope to nope and back again: A new hybrid attention strategy. In D. Belgrave, C. Zhang, H. Lin, R. Pascanu, P. Koniusz, M. Ghassemi, and N. Chen (eds.), Advances in Neural Information Processing Systems, volume 38, pp. 64133– 64157. Curran Associates, Inc., 2025c. URL https://proceedings.neurips.cc/paper_ files/paper/2025/file/5c9ab393551b7a39b4c02d88fe5e7e69-Paper-Conference.pdf. Yechezkel Zalcstein. Locally testable languages. Journal of Computer and System Sciences, 6 (2):151–167, 1972. ISSN 0022-0000. doi: https://doi.org/10.1016/S0022-0000(72)80020-5. URL https://www.sciencedirect.com/science/article/pii/S0022000072800205.

17

Published as a conference paper at COLM 2026

Appendix Contents A Preliminaries: Formal Language Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 A.1 Linear Temporal Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 A.2 First-Order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 A.3 Regular Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 A.4 Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 A.5 The Syntactic Monoid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 A.6 Equivalences between Formalisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 B Proofs: Characterizations of LTL[P, MOD] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 B.1 Inexpressibility Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 C Proofs: Periodic RoPE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 C.1 Component-Periodic Schedules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 C.2 Upper Bounding Periodic RoPE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 C.3 Lower Bounding Periodic RoPE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 C.4 Characterizing Periodic SiPE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 D Proofs: Non-Periodic RoPE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 E Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 E.1 Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 E.2 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 E.3 Periodic-Construction Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 E.4 Conventional Non-Periodic Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 E.5 Detailed Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

A

Preliminaries: Formal Language Theory

We introduced formal languages and linear temporal logic in §2. We now provide the detailed LTL semantics, and introduce the tools that provide a richer understanding of fragments of LTL. We summarize in Tab. 3 known characterizations of relevant fragments of LTL. In §B, we give a proof of the exact characterization of LTL[P, MOD] in terms of polynomials, first-order logic, automata and the syntactic monoid. Our proofs are based on similar characterizations of LTL[P] and LTL[P, F, MOD] (Li & Cotterell, 2025; Dartois & Paperman, 2013). A.1

Linear Temporal Logic

The full semantics for LTL are the following. • w, i |= π a ⇐⇒ wi = a; • w, i |= ψ1 ∨ ψ2 ⇐⇒ w, i |= ψ1 ∨ w, i |= ψ2 ; • w, i |= ψ1 ∧ ψ2 ⇐⇒ w, i |= ψ1 ∧ w, i |= ψ2 ; • w, i |= ¬ψ ⇐⇒ w, i ̸|= ψ; • w, i |= Pψ ⇐⇒ ∃ j < i : w, j |= ψ; • w, i |= Fψ ⇐⇒ ∃ j > i : w, j |= ψ; • w, i |= ψ1 Sψ2 ⇐⇒ ∃ j < i : w, j |= ψ2 and w, k |= ψ1 for all k with j < k < i; • w, i |= ψ1 Uψ2 ⇐⇒ ∃ j > i : w, j |= ψ2 and w, k |= ψ1 for all k with i < k < j; • w, i |= Yψ ⇐⇒ w, i − 1 |= ψ for i > 1; 18

Published as a conference paper at COLM 2026

To define string acceptance, we denote by N + 1 a position outside of the string and define w |= ψ ⇔ w, N + 1 |= ψ. (11) For a set of temporal operators O , we denote by LTL[O] the corresponding fragment of LTL. We say a formula ψ is a LTL[O] formula if it can be written in LTL with only the Boolean connectives and operators from O . S subsumes the left-context-dependent operators P and Y (Gabbay et al., 1980). Example: The language aΣ∗ of strings starting with a specific symbol a can be described by a LTL[P] formula: P (π a ∧ ¬P⊤) (12) The language Σ∗ a of strings ending with a specific symbol a can be described by a LTL[Y] formula: Yπ a (13) The language aΣ∗ a can be described by a LTL[S] definable formula because S can express both P and Y. LTL has become a key tool in characterizing the expressivity of fixed-precision transformers. Softmax transformers, leftmost hard-attention transformers and average hard-attention transformers are equivalent to LTL[P] (Li & Cotterell, 2025; Jerad et al., 2025), while rightmost hard-attention transformers are equivalent to full LTL[S] (Yang et al., 2024). As formalized in §2, LTL can be extended with modular predicates, denoted by LTL[O , MOD] for a set of operators O . A.2

First-Order Logic

First-order logic (FO[<]) can also be used to characterize subregular classes. FO[<]’s building blocks are atomic formulas, denoted by the unary predicate π a for all a ∈ Σ and the binary predicate < which determines the order between string positions. We have π a (i ) = ⊤ if and only if wi = a. Building on these atomic formulas, FO[<] operates on variables, which denote positions of the input string. In FO[<], a variable is either free or bounded by a quantifier. For example, in the existential quantification ∃i < j, i is a bounded variable while j is a free variable. FO[<] formulas are then constructed inductively as follows. (1) Every atomic formula is an FO[<] formula; (2) A Boolean combination of FO[<] formulas is an FO[<] formula; (3) If ϕ(i . . .) is an FO[<] formula, then so is ∃i : ϕ(i . . .)2 . Let ϕ be a formula without any free variables. We say w |= ϕ if ϕ is satisfied when evaluating def it on w. ϕ induces a language, which we denote by L(ϕ) = {w ∈ Σ∗ | w |= ϕ}. Fragments of FO[<]: We denote by FO2 [<] the fragment of FO[<] restricted to using at most two distinct variables in any sub-formula. We denote by PFO2 [<] the past fragment of FO2 [<] in which formulas are restricted so that whenever a free variable i is present, every quantifier must be of the form ∃ j : j < i or ∀ j : j < i. In other words, only past positions relative to the free variable are accessed. PFO2 [<] formulas can be inductively written as follows. (1) Every atomic formula is a PFO2 [<] formula; (2) A Boolean combination of PFO2 [<] formulas is a PFO2 [<] formula if it does not contain more than two variables; (3) If ϕ(i, j) is a PFO2 [<] formula with two free variables i, j, ∃i < j : ϕ(i, j) and ∃ j < i : ϕ(i, j) are PFO2 [<] formulas; 2 The universal quantifier ∀ is constructed by applying negation to the existential quantifier.

19

Published as a conference paper at COLM 2026

(4) If ϕ(i ) is a PFO2 [<] formula with one free variable i, ∃i < j : ϕ(i ) is a PFO2 [<] formula; (5) If ϕ(i ) is a PFO2 [<] formula with one free variable i, ∃i : ϕ(i ) is a PFO2 [<] formula. Over finite strings, PFO2 [<] and LTL[P] define the same languages (Li & Cotterell, 2025), while FO[<] is equivalent to the full star-free class, which is LTL[S] (Kamp, 1968; McNaughton & Papert, 1971; Gabbay et al., 1980). We therefore use LTL[P] in the main narrative and retain PFO2 [<] when invoking first-order, automata-theoretic, or algebraic characterizations. Modular predicates. Akin to LTL, FO[<] can be extended with unary modular predicates, albeit with a slight modification to its LTL counterpart. In LTL, formulas are evaluated at position N + 1, meaning LTL can robustly make statements about the residue class of N, the length of the string. Because FO[<] formulas are evaluated by ranging variables over the entire string, such an operator cannot be directly implemented with unary predicates. Therefore, 0-ary predicates MODrm are needed, where MODrm is true if and only if the length of the input string N is congruent to r modulo m. Adding these modular predicates to first-order fragments gives PFO2 [<, MOD], FO2 [<, MOD], and FO[<, MOD]; as shown in §3.4, LTL[P, MOD] and PFO2 [<, MOD] define the same class of languages. A.3

Regular Expressions

Regular expressions are a declarative formalism for describing languages, defined recursively: (1) ε and each w ∈ Σ is a regular expression; (2) If α and β are regular expressions, so are the union α + β, concatenation αβ, complement α C and the Kleene closure α∗ . A language is regular if it can be described by a regular expression. A regular language is star-free if it can be described by a regular expression without the Kleene operator. Definition A.1. A monomial over an alphabet Σ is a language described via a regular expression of the form: Σ0∗ w1 Σ1∗ . . . w N Σ∗N (14) Where Σ0 , Σ1 . . . ⊆ Σ and w1 , w2 . . . ∈ Σ. Definition A.2. A left-deterministic monomial is a monomial where for every 0 < i ≤ N, wi ̸∈ Σi−1 . A right-deterministic monomial is a monomial where for every 0 < i ≤ N, wi ̸∈ Σi . An unambiguous monomial is a monomial that is either left-deterministic or right-deterministic. Example: The language aΣ∗ of strings starting with the symbol a is a left-deterministic monomial, since the marker a does not appear in the preceding empty block (a ∈ / Σ0 ). Symmetrically, the language Σ∗ a of strings ending with the symbol a is a rightdeterministic monomial. Both aΣ∗ and Σ∗ a are therefore unambiguous monomials. Their intersection aΣ∗ ∩ Σ∗ a = aΣ∗ a is an unambiguous monomial. A polynomial is a finite union of monomials. A left-deterministic (resp., right-deterministic, unambiguous) polynomial is a finite union of left-deterministic (resp., right-deterministic, unambiguous) monomials. To adapt our analysis to RoPE transformers, we now introduce modular polynomials (Dartois & Paperman, 2013). Definition A.3. A monomial over Σ is modular with respect to some integer d if it can be written as: (Σ0,0 Σ0,1 . . . Σ0,d−1 )∗ w1 (Σ1,0 Σ1,1 . . . Σ1,d−1 )∗ . . . w N (Σ N,0 Σ N,1 . . . Σ N,d−1 )∗ (15) Where: • Each marker wi occurs at a position congruent to some ri modulo d; 20

Published as a conference paper at COLM 2026

• Each Σi,j is some subset of Σ; • For every i and every position p lying in the i’th block, the symbol at position p belongs to Σi,p mod d Note that the standard monomial is recovered with d = 1. Definition A.4. A left-deterministic modular monomial is a modular monomial such that for every 0 < i ≤ N, wi ∈ / Σi−1,ri . As before, we similarly define unambiguous modular monomials, unambiguous modular polynomials and left-deterministic modular polynomials. A.4

Automata

The standard formalism for (sub)regular languages are finite automata—machines that transition within finitely many states. Definition A.5. A semiautomaton A is a 3-tuple (Σ, Q, δ) where Σ is an alphabet, Q is a finite set of states and δ : Q × Σ → Q is a transition function. We further define an initialized semiautomaton as a semiautomaton with an initial state. Definition A.6. A deterministic finite automaton (DFA) A is a 5-tuple (Σ, Q, qι , F, δ) where (Σ, Q, δ) is a semiautomaton, qι ∈ Q is an initial state, and F ⊆ Q is a set of final states. We now introduce the automata that characterize the class of languages described by PFO2 [<]. Intuitively, because quantifiers in PFO2 [<] can only look backward, they can only accumulate information about the past. We now introduce a class of automata that mirror this behavior: Their states are partially ordered and transitions may only move upward in this order. Consequently, reading a symbol can only refine what the automaton knows about the prefix read so far—no information can be discarded, and no state can be revisited. Definition A.7. Let δ∗ : Q × Σ∗ → Q be the transitive closure of δ, defined as δ∗ (q, w) = δ(q, w), for w ∈ Σ

(16a)

∗

(16b)

∗

δ (q, w1 · · · w N ) = δ(δ (q, w1 · · · w N −1 ), w N )

with δ∗ (q, ε) = q for any q ∈ Q. A partially ordered DFA (PODFA) is a DFA A = (Σ, Q, qι , F, δ) where there is a partial order relation ⪯ on Q defined as q ⪯ p if and only if δ∗ (q, w) = p for some string w ∈ Σ∗ . As an example, the language of strings that contain the symbol a over any alphabet can be modeled by the following PODFA. a, b

b a q0

q1

Figure 4: PODFA for Σ∗ aΣ∗ over Σ = { a, b}. The partial order q0 ⪯q1 holds since q1 is reachable from q0 but not vice versa. To link automata with modular predicates, we now introduce the k-automaton of some given automaton. In first-order logic with modular predicates, strings can be evaluated to the same value up to a modulus. For some modulus k, we therefore consider k-automata where strings are read as blocks of k symbols. def

Definition A.8. Let A = (Σ, Q, qι , F, δ) be a DFA. Let k be an integer. We define Ak = (Σk , Q, qι , F, δk ) as the k-automaton of A where: def

• Σk = {w | |w| = k and w ∈ Σ∗ } 21

Published as a conference paper at COLM 2026

def

• δk (q, w1 w2 . . . wk ) = δ(. . . δ(δ(q, w1 ), w2 ), wk ). We denote by PODFAk the set of automata such that their k-automaton are PODFAs. As an example, ( ab)∗ is the language of an automaton A in PODFA2 , as seen in Fig. 5. a q0

q1 b b

w ∈ Σ2

ab

a

q0

Rej

aa, ba, bb

Rej

a, b

Figure 5: Minimal automata for ( ab)∗ and its corresponding 2-automaton.

A.5

The Syntactic Monoid

The syntactic monoid is a tool that partitions Σ∗ into classes of strings, where each class contains strings that all contain the same syntactic information with respect to a given regular language. We now formalize the syntactic monoid of a language. Definition A.9. A monoid M is a set equipped with a binary operation and an identity element. For instance, the free monoid is the set Σ∗ equipped with the concatenation operation and the empty string ε as identity. Definition A.10. A monoid M is in R if and only if for all w1 , w2 , w3 ∈ M, w1 w2 w3 = w1 implies w1 w2 = w1 . A monoid M is in L if and only if for all w1 , w2 , w3 ∈ M, w3 w2 w1 = w1 implies w2 w1 = w1 . Definition A.11. The syntactic congruence ⪯L is the equivalence relation on Σ∗ given the language L such that for all x, y ∈ Σ∗ , we have x⪯L y if and only if: sxz ∈ L ⇐⇒ syz ∈ L ∀s, z ∈ Σ∗

(17)

Given a language, the syntactic congruence partitions strings of Σ∗ into classes such that they are syntactically equivalent with respect to the language’s automaton. Example: Consider the language PARITY (introduced in §3.4) and its syntactic congruence ⪯L . ⪯L then has exactly two congruence classes, one for strings with an even numbers of 1s (which we denote by Ceven ) and another for strings with an odd number of 1s (which we denote by Codd ). Example strings in each class are: 011, 1111, 0101 ∈ Ceven 1, 10011, 1101 ∈ Codd Definition A.12. Let M be the free monoid, L be a regular language and ⪯L its syntactic congruence. The syntactic monoid of L is the quotient monoid M/⪯L . Interestingly, the syntactic monoid of a regular language is isomorphic to the transition monoid of the minimal automaton accepting the language. Finally, we now extend the monoid class R to account for modularity. Definition A.13. Let M be the syntactic monoid of a regular language L with associated automaton A. Let Mk be the syntactic monoid of the language associated with Ak , the k-automaton. Then, M is in QR if and only if there exists an integer k such that Mk is in R. 22

Published as a conference paper at COLM 2026

A.6

Equivalences between Formalisms

To conclude this section, we summarize in Tab. 3 the known characterizations of FO2 [<, MOD] and PFO2 [<], and introduce the analogous characterization of PFO2 [<, MOD] which we prove in §B. First-order logic

LTL

Regular expression

Syntactic Monoid

Automata

Note

FO2 [<, MOD]

LTL[P, F, MOD]

Unambiguous modular

QDA

2-PODFAk

Dartois & Paperman (2013)

PFO2 [<]

LTL[P]

Leftdeterministic

R

PODFA

Brzozowski & Ellen (1980) and Li & Cotterell (2025)

PFO2 [<, MOD]

LTL[P, MOD]

Leftdeterministic modular

QR

PODFAk

§B

Table 3: Characterizations of fragments of first-order logic. The equivalences in the last row are novel.

B

Proofs: Characterizations of LTL[P, MOD]

In this section, we provide a rich characterization of LTL[P, MOD] via the following theorem. Theorem 3.3. Let L ⊆ Σ∗ be a regular language, M be its syntactic monoid, and A be the minimal DFA accepting it. The following assertions are equivalent: (i) L is a left-deterministic modular polynomial (ii) M ∈ QR (iii) ∃k ∈ N such that Ak is partially ordered (iv) L = L(ϕ) for some PFO2 [<, MOD] formula ϕ (v) L = L(ψ) for some LTL[P, MOD] formula ψ Most of the following lemmata are adaptations from equivalences proven in prior work (Dartois & Paperman, 2013; 2015; Li & Cotterell, 2025) applied on different fragments of first-order logic. Lemma B.1. A language L has its syntactic monoid in QR if and only if there exists a k such that L’s automaton belongs to PODFAk . Proof. By definition, a language L has its syntactic monoid in QR if and only if there exists a k such that its k-automaton Ak has its syntactic monoid in R. The equivalence between the transition monoid of Ak being in R and Ak being a PODFA follows from Brzozowski & Ellen (1980). Therefore, L’s automaton belongs to PODFAk for some k. ■ Lemma B.2. If ϕ is a PFO2 [<, MOD] formula, then the syntactic monoid of ϕ’s language is in QR. If a language’s syntactic monoid is in QR, it is the language of some PFO2 [<, MOD] formula. Proof. The regular languages with a syntactic monoid in R are exactly the PFO2 [<] languages (Li & Cotterell, 2025). Moreover, for any logic characterized by a local variety V, augmenting the logic with modular predicates yields a logic characterized by QV (Dartois & Paperman, 2015). Since PFO2 [<] is characterized by R and R is local (Almeida, 2025), augmenting PFO2 [<] with modular predicates gives the class characterized by QR. ■ 23

Published as a conference paper at COLM 2026

Lemma B.3. PFO2 [<, MOD] and LTL[P, MOD] characterize the same class of languages. Proof. The equivalence without modular predicates has already been proven via structural induction (Li & Cotterell, 2025). Adding the same unary predicate MOD to both logics therefore preserves the equivalence. It remains to show that unary modular predicates in LTL[P, MOD] can express 0-ary predicates in PFO2 [<, MOD]. Formulas in LTL[P] are evaluated at the string position N + 1. Moreover, N is congruent to r modulo m if and only if N + 1 is congruent to r + 1 modulo m. Therefore, evaluating in LTL[P, MOD] the unary modular predicate MODrm+1 at N + 1 is equivalent to evaluating the 0-ary predicate MODrm in PFO2 [<, MOD]. ■ To prove the equivalence between PFO2 [<, MOD] and left-deterministic modular polynomials, we consider languages over enriched alphabets (Dartois & Paperman, 2013). We denote by PFO2 [<, MODd ] the restriction of PFO2 [<, MOD] with congruences modulo d. For any PFO2 [<, MOD] formula, there exists an integer d such that the formula is also PFO2 [<, MODd ]-definable—by for example setting d as the least common multiplier of all the moduli used. def

Definition B.1 (Enriched alphabets; Dartois & Paperman 2013). The set Σd = Σ × (Z/dZ) def is the enriched alphabet of Σ, where Z/dZ = {0, 1, . . . , d − 1}. The projection proj : Σ∗d → Σ∗ removes the (Z/dZ) component of every symbol ( a, i ) ∈ Σd of strings in Σ∗d . Definition B.2 (Well-formed words; Dartois & Paperman 2013). Given some alphabet Σ, the enriched word (w0 , i0 ) . . . (w N , i N ) is well-formed if i j ≡ j (mod d) for all 0 ≤ j ≤ N. We denote by K ⊂ Σ∗d the set of well-formed words. Note that on K, the projection operator proj is a bijective application. Indeed, every word w = w0 · · · w N ∈ Σ∗ has a unique preimage in K: the word (w0 , 0 mod d) · · · (w N , N mod d) obtained by annotating each position j with j mod d. Surjectivity is immediate, and injectivity holds because distinct well-formed words over Σd differ in at least one symbol and therefore project to distinct words. We can now describe PFO2 [<, MOD] with enriched alphabets.3 Proposition B.1. PFO2 [<, MODd ](Σ∗ ) = proj(PFO2 [<](Σ∗d ) ∩ K ) Proof. The statement has been shown to be true for FO2 [<, MOD] (Dartois & Paperman, 2013). The result does not depend on how the binary predicate < is used, and therefore it also holds for PFO2 [<, MOD]. Modular predicates of the form MODrd can be computed by disjuncting over all atomic formulas of the form π(w,r) in PFO2 [<](Σ∗d ) ∩ K for all w ∈ Σ. For the converse, formulas over exclusively well-formed words can be equivalently described by formulas over words in Σ∗ with modular predicates. For instance, π(w,r) in PFO2 [<](Σ∗d ) ∩ K can be written as πw ∧ MODrd in PFO2 [<, MODd ](Σ∗ ). ■ We can now prove the following lemma. Lemma B.4. A language is a left-deterministic modular polynomial if and only if it can be described by a PFO2 [<, MOD] formula. Proof. Recall that for any PFO2 [<, MOD] formula describing a language L, there exists a PFO2 [<, MODd ] formula, for some integer d, that also describes L. By Prop. B.1, L is therefore the projection of the well-formed words of a language L′ definable by a PFO2 [<](Σ∗d ) formula. It remains to be shown via this projection that L can be equivalently described with a left-deterministic polynomial. 3We may write PFO2 [<](Σ∗ ) to specify that the logic is being used over the alphabet Σ.

24

Published as a conference paper at COLM 2026

Because L′ is definable by a PFO2 [<](Σ∗d ) formula, it is a disjoint union of left-deterministic monomials over Σd (Li & Cotterell, 2025). Recall that over well-formed strings, proj is a bijection. Therefore, proj preserves disjoint unions. It thus suffices to show that proj maps each left-deterministic monomial over Σd to a left-deterministic modular monomial over Σ, and conversely. Fix an enriched monomial M = Ξ0∗ w1 Ξ1∗ . . . w N Ξ∗N over Σd , where Ξi ⊆ Σ × (Z/dZ) and wi = (wi , ri ) for all 0 ≤ i ≤ N, and set def

Σi,j = {w | (w, j) ∈ Ξi }. We claim that the projection of the well-formed words of M is exactly the modular monomial determined, in the sense of Def. A.3, by the markers wi , the residues ri , and the subsets Σi,j . Forward (⇒). Let w = proj(w) for a well-formed w ∈ M, factored as w = u0 w1 u1 . . . w N u N with ui ∈ Ξi∗ . Projecting yields u = u0 w1 u1 . . . w N u N . Well-formedness places wi = (wi , ri ) at a position ≡ ri (mod d), so each wi stands at residue ri in u. For any position p inside the block ui , its enriched letter is (w, p mod d) ∈ Ξi , hence w ∈ Σi, p mod d . Thus u satisfies both conditions of Def. A.3 and lies in the modular monomial. Reverse (⇐). Conversely, any u in that modular monomial admits a factorization meeting the same two conditions; tagging each position p of u with p mod d produces the unique well-formed preimage u with proj(u) = u, and those conditions place u in M. No rotation or partial-block bookkeeping arises, since Def. A.3 is stated over global positions and already absorbs each block’s residue offset. Finally, left-determinism transfers in both directions: for every 0 < i ≤ N, wi ∈ / Ξi−1 ⇐⇒ (wi , ri ) ∈ / Ξi−1 ⇐⇒ wi ∈ / Σi−1, ri , the right-hand side being exactly the condition of Def. A.4. Hence M is left-deterministic if and only if its projected modular monomial is left-deterministic, and proj restricts to a bijection between left-deterministic monomials over Σd and left-deterministic modular monomials over Σ. Applying this correspondence to each term of the disjoint union describing L′ , together with Prop. B.1, shows that L is in PFO2 [<, MOD] if and only if it is a left-deterministic modular polynomial. ■ B.1

Inexpressibility Results

Proposition B.2. The locally testable language Σ∗ abΣ∗ with |Σ| > 2 is not in LTL[P, MOD] = PFO2 [<, MOD] = SMAT[RoPEP ]4 . Proof. Consider the minimal DFA A for Σ∗ abΣ∗ with the alphabet Σ = { a, b, c}, illustrated in Fig. 6.

b, c

a, b, c

a b

a q0

q1

q2

c Figure 6: Minimal DFA for Σ∗ abΣ∗ over Σ = { a, b, c}

A1 = A can be seen to not be partially ordered. Consider some integer k > 1 and the k-automaton Ak of A. Let wa ∈ Σk be a string of k times the symbol a, and wc ∈ Σk a string 4 Note that over the two-letter alphabet Σ

= { a, b}, Σ∗ abΣ∗ is in PFO2 [<] and thus also in

2

PFO [<, MOD].

25

Published as a conference paper at COLM 2026

of k times the symbol c. We have that δk (q0 , wa ) = q1 and δk (q1 , wc ) = q0 . Therefore, there is no partial order on the states of Ak as q0 and q1 are mutually reachable. Thus, for any integer k, Ak can never be partially ordered, and Σ∗ abΣ∗ ̸∈ PFO2 [<, MOD] for |Σ| > 2. ■ Proposition B.3. PARITY is not in LTL[P, MOD] = PFO2 [<, MOD] = SMAT[RoPEP ]. Proof. Consider the minimal DFA A for PARITY, illustrated in Fig. 7. 0

0 1

q0

q1 1

Figure 7: Minimal DFA for PARITY over Σ = {0, 1}

A1 = A can be seen to not be partially ordered. Consider some integer k > 1 and the k-automaton Ak of A. Let w be a string of length k with an odd number of 1s. We have that δk (q0 , w) = q1 and δk (q1 , w) = q0 . Therefore, there is no partial order on the states of Ak as q0 and q1 are mutually reachable. Thus, for any integer k, Ak can never be partially ordered, and PARITY ̸∈ PFO2 [<, MOD]. ■

C

Proofs: Periodic RoPE

This section supplies the full proofs for periodic RoPE and for both inclusions summarized in §3: first SMAT[RoPEP ] ⊆ PFO2 [<, MOD], and then LTL[P, MOD] ⊆ SMAT[RoPEP ]. In all the following proofs, we follow the integer indexing convention for arrays: For v ∈ FD and a finite set of integers {i1 , · · · in }, v[i1 , · · · in ] ∈ Fn is the vector of elements in v indexed by i1 , · · · i n . C.1

Component-Periodic Schedules

b is componentProposition 2.1 (Component-periodicity via MOD). If a realized RoPE schedule Θ periodic, then its image is finite and, for every matrix coordinate and realized value, the positions attaining that value are definable by unary modular predicates.

def b periods and Proof. Let m1 , . . . ,m D/2 be component n o M = lcm (m1 , . . . , m D/2 ). Then Ri+ M = b i , so the image is contained in R b0, . . . , R b M−1 . For a matrix coordinate c and realized R n o def b a [c] = v . Then value v, define Ac,v = a ∈ {0, . . . , M − 1} : R

b i [c] = v R

⇐⇒

_

MODaM (i ) .

(18)

a∈ Ac,v

Thus every entry-value relation is definable with unary modular predicates.

■

Proposition 2.2 (Rational-angle functions are periodic). If θd / (2π ) = ad /md ∈ Q, then i 7→ Rotθd ,i has period md . 26

Published as a conference paper at COLM 2026

Proof. We consider the mapping for cosine, as the sine analysis is the same. For some i ∈ N, we have:   2πθd cos (θd i ) = cos i (19a) 2π   a = cos 2π d i (19b) md   a = cos 2π d i + 2ad π (19c) md   a = cos 2π d (i + md ) (19d) md = cos (θd (i + md )) (19e) Therefore, cos (θd i ) is periodic with integer period md . C.2

■

Upper Bounding Periodic RoPE

Lemma 3.1. Any F-transformer with RoPEP can be simulated by PFO2 [<, MOD]. SMAT[RoPEP ] ⊆ PFO2 [<, MOD] = LTL[P, MOD].

Hence,

Proof. We formalize what it means for PFO2 [<, MOD] to simulate a transformer. Definition C.1 (Li & Cotterell 2025, Definition B.1.). A function λ : (Σ)∗ → (FD )∗ is said to be simulated by PFO2 [<, MOD] if for every dimension d ∈ [ D ] and every floating-point value f ∈ F, there exists a single-variable formula ϕ in PFO2 [<, MOD] such that for every position i ∈ [ N ]: λ(w)d,i = f ⇐⇒ w, i |= ϕ

(20)

Similarly, we can define the simulation of a matrix-valued function via a two-variable PFO2 [<, MOD] formula. We prove that PFO2 [<, MOD] can simulate any RoPEP transformer. First, each realized matrix entry can be simulated by the formulas from Prop. 2.1. b i can be seen as a function mapping positions i to elements in A realized rotation matrix R FD× D . For every matrix coordinate c ∈ [ D × D ] and floating-point value f ∈ F, we define a PFO2 [<, MOD] formula ϕc, f such that: b i [c] = f ⇐⇒ w, i |= ϕc, f R

(21) def

b i , we create constant formulas ϕ⊤ = ⊤ and 0-elements of the matrix: For the 0-elements of R def ϕ⊥ = ⊥. If the floating-point value f is 0, we assign the constant formula ϕ⊤ . Otherwise, we assign ϕ⊥ . Position-dependent elements of the matrix. For every coordinate c and realized value v, W b i [c] = v (Prop. 2.1). This covers every the formula a∈ Ac,v MODaM (i ) is true exactly where R block entry without recovering an ideal angle from its finite-precision realization. Therefore, we can simulate the rotation matrices with PFO2 [<, MOD]. Omitting the periodic rotations, all other components of a fixed precision soft-attention transformer can be simulated by PFO2 [<] (Li & Cotterell, 2025). Finally, as the elements of the rotation matrices belong to a finite set (due to Prop. 2.1), the rotation matrices belong themselves to some finite set. Therefore, the rotation of the keys and queries is a mapping between two finite sets. Any mapping between finite sets can be simulated via a disjunction over the finitely-many inputs in the domain that lead to some output in the image (Chiang et al., 2023; Li & Cotterell, 2025). This concludes the proof. ■ 27

Published as a conference paper at COLM 2026

Proposition 3.1. Binary modular predicates can be expressed with unary modular predicates and Boolean logic. Proof. We will show that MODrm (i, j) can be written as the following finite disjunction. MODrm (i, j) =

m_ −1

( a+r ) mod m

a (MODm (i ) ∧ MODm

( j))

(22)

a =0

We denote by i0 and j0 the residues such that i ≡ i0 (mod m) and j ≡ j0 (mod m). MODrm (i, j) = ⊤ if and only if ( j − i ) ≡ r (mod m). Equivalently, ( j0 − i0 ) ≡ r (mod m), i.e. j0 ≡ r + i0 (mod m). Therefore, MODrm (i, j) = ⊤ if and only if there exist residues i0 and j0 such that 1) i ≡ i0 (mod m) 2) j ≡ j0 (mod m) with j0 ≡ i0 + r (mod m). This statement is exactly the right hand side of the given equation. ■ C.3

Lower Bounding Periodic RoPE

On finite precision. Before proving the lower bound LTL[P, MOD] ⊆ SMAT[RoPEP ], we recall that our result holds for some finite-precision regime F. In other words, we design a tailored finite set of values F that works for our constructions. This assumption is implicitly made in related work (Yang et al., 2024). This allows us to assume that the finitely many values our constructions manipulate are exactly representable, i.e. are present in F. For each modulus m, we specify the required roots of unity directly as an m-entry rotation table and include its finitely many entries in F. A cyclic counter or modular index return the corresponding table entry. This establishes an exact result in the abstract expressivity model; it does not assert that standard floating-point hardware represents 2π/m, the corresponding roots of unity, or the unbounded product 2πi/m exactly. The experiments in §3.5 test a practical finite-precision implementation empirically. Lemma 3.2. For every LTL[P, MOD] formula, there is an F-transformer with RoPEP that simulates the formula. Hence LTL[P, MOD] ⊆ SMAT[RoPEP ]. Proof. We formalize what it means for SMAT[RoPEP ] to simulate a LTL[P, MOD] formula. Definition C.2 (Li & Cotterell 2025, Definition B.9.). A LTL[P, MOD] formula ψ is simulated by a function λ : (Σ)∗ → (FD )∗ if there exists a coordinate d ∈ [ D ] such that for every input string w ∈ (Σ)∗ and string position i ∈ [ N ]:  1 if w, i |= ψ λ(w)d,i = (23) 0 otherwise We proceed by structural induction on the LTL[P, MOD] formula. Induction on LTL[P] without MOD. Any LTL[P] formula can be simulated by a transformer (without PEs) via structural induction on its constituents (Li & Cotterell, 2025). To lift this to SMAT[RoPEP ], we allocate dedicated dimensions for the Boolean connectives and P—the sole temporal operator of LTL[P]—and set their rotation angles to 0 (identity matrices), so that RoPE has no effect on those dimensions. We then apply Li & Cotterell’s (2025) simulation directly, yielding LTL[P] ⊆ SMAT[RoPEP ]. Simulating modular predicates. It remains to realize each modular atom. Consider the formula MODrm (i ). We isolate the case i = 1, where MODrm (1) is then a compile-time constant. The first position can be flagged by performing uniform attention over the strict left context and checking the count is exactly 1, which we assume is in F. We can then store MODrm (1) at that position. Moreover, the case m = 1 is the constant-true predicate, so we proceed to the m ≥ 2, i ≥ 2 case. 28

Published as a conference paper at COLM 2026

We first allocate one rotary pair at dimensions d, d + 1 with the exact period-m lookup table (see §2.4) def b (d) def Tm (s) = Rot2π/m,s (0 ≤ s < m) , R = Tm (i mod m) , i (24) def def δm = min (1 − cos (2πs/m)) > 0, bm = 1 − δm /2. 1≤ s < m

We also allocate one unrotated pair of dimensions d′ , d′ + 1. All other dimensions are unused (i.e., manually set to 0 in keys and queries) in our construction. Query. Before the rotations, we set the elements of the query projection to positionindependent constants. These constants are implemented by setting the query weight matrix Q to a zero-matrix and encoding the desired values in the query bias vector bq , so that Qxiℓ + bq = bq for all inputs xiℓ .   cos (2πr/m) ℓ ( Qxi )[d, d + 1] = − sin (2πr/m)   1 ( Qxiℓ )[d′ , d′ + 1] = 0 The post-rotation query dimensions then become:   
2πi cos cos 2πr + sin( 2πi ) sin m m ℓ  m qi [d, d + 1] = 
2πr 2πi sin( 2πi sin m ) cos m − cos m   1 qiℓ [d′ , d′ + 1] = 0



2πr m 
2πr m

Key. We set the pre-rotation dimensions of the key vector as follows.   C1{w j = BOS } ℓ (Kx j )[d, d + 1] = 0   Cbm (1 − 1{w j = BOS }) ℓ ′ ′ (Kx j )[d , d + 1] = 0 Where C is a positive constant in F defined later, and 1{w j = BOS } can be computed via a feedforward network. Note that because BOS correspond to position 0, the dimensions d, d + 1 are unaffected by rotation: At BOS the rotation is an identity mapping, at a symbol position the vector is a 0-vector. Moreover, the dimensions d′ , d′ + 1 are by construction unrotated. Score. The query–key computation score yields:  C cos (2π (i − r ) /m) , (qiℓ )⊺ kℓj = Cbm ,

if w j = BOS otherwise

(25)

Notice that cos (2π (i − r ) /m) is maximized when i ≡ r (mod m). Modular predicate condition satisfied. If i ≡ r (mod m), the score with BOS is C and the scores with non-BOS positions are all C (1 − δm /2). Therefore, the largest score is C by a margin of Cδm /2. Modular predicate condition not satisfied. Suppose i ̸≡ r (mod m). Then cos (2π (i − r )/m) ≤ 1 − δm by definition of δm , so the score with BOS satisfies C cos (2π (i − r )/m) ≤ C (1 − δm ). Every non-BOS position still scores exactly Cbm = C (1 − δm /2), independently of j. Hence every non-BOS position now beats BOS, by a margin of at least C (1 − δm /2) − C (1 − δm ) = Cδm /2.

(26)

So, in either case (i ≡ r (mod m) or not), whichever side wins—BOS or the (tied) non-BOS positions—does so by a margin of at least Cδm /2. 29

Published as a conference paper at COLM 2026

Choosing C and extracting the predicate. We define the value vector to be 1 at BOS and 0 at every other position, so that the attention output at position i is exactly αi,BOS . Selecting C ≥ 2 f large /δm makes the margin Cδm /2 established above at least f large in both cases. By stable softmax (§2), subtracting the maximum score from every score leaves an exponent of 0 at every position attaining the maximum and an exponent at most − f large —hence rounding to exp(− f large ) = 0—at every position on the losing side of the margin. • If i ≡ r (mod m): BOS uniquely attains the maximum score, so αi,BOS = 1 and αi,j = 0 for every non-BOS j. The attention output is 1. • If i ̸≡ r (mod m): Every non-BOS position attains the (tied) maximum score, so αi,BOS = 0, while the non-BOS weights αi,j absorb the remaining mass. The attention output is still αi,BOS = 0, regardless of how stable softmax splits weight among the tied non-BOS positions. The attention output then equals 1{MODrm (i )}: The rotary pair d, d + 1 supplies the positiondependent score against BOS, while the unrotated pair d′ , d′ + 1 supplies the constant nonBOS baseline Cbm that this score is compared against, and together they correctly compute MODrm (i ). Completing the induction. A formula contains only finitely many modular atoms, so it requires finitely many rotary pairs and constants. Choose F to contain the entries of their finite lookup tables and all displayed intermediate values. This completes the induction. ■ C.4

Characterizing Periodic SiPE

Theorem 3.2. SMAT[SiPEP ] = LTL[P, MOD] = PFO2 [<, MOD]. Proof. We now show both directions of the equivalence. Forward (⇒). Every non-PE component of a SMAT[SiPEP ] transformer is in PFO2 [<] (Li & Cotterell, 2025). Periodic sinusoidal position encodings can also be expressed via unary modular predicates by Prop. 2.1, yielding the inclusion in PFO2 [<, MOD]. Reverse (⇐). NoPE transformers, which are subsumed by SMAT[SiPEP ] transformers, can express PFO2 [<]. Simulating modular predicates can be done by processing sinusoidal position encodings with feedforward networks (Yang et al., 2024) using an appropriate schedule and pre-computed lookup table (§2.4), leading to the reverse direction. Note that Yang et al.’s (2024) modular predicate simulation does not rely on the attention type. ■

D

Proofs: Non-Periodic RoPE

Because Cor. 4.1 certifies the simulation only up to a finite length, we first record the length-bounded variant of Def. C.2 that it uses. Definition D.1 (Bounded-length simulation). Let L ∈ N. A formula ψ is L-simulated by a function λ : (Σ)∗ → (FD )∗ if there exists a coordinate d ∈ [ D ] such that for every input BOS w EOS with |w| ≤ L and every position i ∈ [|w| + 1],  1 if w, i |= ψ λ ( BOS w EOS )d,i = (27) 0 otherwise. Taking L → ∞ recovers Def. C.2. Throughout, positions are indexed so that BOS occupies position 0, the string occupies positions 1, . . . , |w|, and EOS occupies position |w| + 1, which is the readout position. Hence |w| ≤ L makes every query position at most L + 1, which is exactly the range quantified over in Eq. (10). 30

Published as a conference paper at COLM 2026

Corollary 4.1. Fix g, C, and F, and let L ∈ N. Write SMAT[RoPENP ]-transformers for softattention RoPENP transformers with unrotated subspaces, and let L-simulation be as in Def. D.1. (k)

(i) For every offset k ≥ 1 with k ≤ L ≤ Nmax ( g, C, F), such a transformer L-simulates the fixed-offset operator Yk . (1)

(ii) If 1 ≤ L ≤ Nmax ( g, C, F), it L-simulates every LTL[P, Y]-definable formula. More gen(k)

erally, for a finite set of offsets K ⊆ N≥1 with max K ≤ L ≤ mink∈K Nmax ( g, C, F), it L-simulates every formula built from atomic predicates, Boolean connectives, P, and the operators {Yk : k ∈ K }. (iii) Moreover, for every L ∈ N and every finite offset set K there exist a rotation angle g with g/ (2π ) ∈ / Q, scales C, and a finite-precision regime F satisfying the hypothesis of (ii). Proof. Allocate unrotated dimensions to the standard structural-induction simulation of LTL[P] (Li & Cotterell, 2025). Fix k ≥ 1. To simulate a Yk ψ subformula directly, use one rotary pair d, d + 1 in a dedicated attention head, with query bias C (cos (kg) , − sin (kg)) and key bias (1, 0) at those two coordinates. In this head we set Q and K to the zero matrix and set every coordinate of bq and bk outside the pair d, d + 1 to 0. The score is therefore exactly the contribution of that pair: The unrotated dimensions carrying the LTL[P] simulation, and every other rotary pair, contribute 0 to it. In particular the biases are the head’s only source of query and key content, so the score is position-dependent but content-independent, as the fixed-offset semantics of Yk requires. After rotation at query position i and key position j, exact arithmetic gives g,C,k

Si,j

= C cos ( g (i − k − j)) ,

(28) g,C,k,F

which is Eq. (9). Under the model’s actual arithmetic, denote the realized score by Sbi,j as in Eq. (10). Store the truth value of ψ in the value vector at each string position and store 0 at BOS. (k)

We prove (i). Fix k ≤ L ≤ Nmax ( g, C, F). At every k + 1 ≤ i ≤ L + 1, position i − k beats (k)

every other key by at least f large , by the definition of Nmax ; note that the competing keys include BOS at j = 0, whose rotation matrix is the identity, so its key is (cos 0, sin 0) = (1, 0). Stable softmax therefore assigns weight 1 to i − k and 0 elsewhere, so the head returns the truth value of ψ exactly k positions earlier. Since i ≥ k + 1, the attended position i − k is a string position, not BOS. At the boundary i ≤ k, the semantics require Yk ψ to be false. The unrotated construction simulates the gate Pk ⊤  , whichholds exactly when i > k—indeed P⊤

holds at i iff i > 1, and inductively Pk ⊤ = P Pk−1 ⊤ holds at i iff some j < i has j > k − 1, i.e. iff i > k; a feedforward Boolean conjunction with this gate therefore suppresses the arbitrary attention output at those boundary positions, mapping it to 0 regardless of its value. This L-simulates Yk , proving (i).

For (ii), every LTL[P, Y] formula is built from atomic predicates, Boolean connectives, P, and Y, so it needs only the offset k = 1: one layer per Y occurrence, applying (i) with k = 1, (1)

which is available because L ≤ Nmax ( g, C, F) by hypothesis. Together with the unrotated P and Boolean constructions this completes the structural induction. For a finite offset set (k)

K, give each k ∈ K its own head and rotary pair; the hypothesis L ≤ mink∈K Nmax ( g, C, F) makes (i) available for every k ∈ K simultaneously, and max K ≤ L makes each application well posed. For (iii), fix any finite L and finite collection of offsets, and choose g/ (2π ) ∈ / Q. Then δL ( g) > 0. Choose the scales C and a finite-precision regime jointly so that CδL ( g) ≥ f large for every corresponding head and all parameters and intermediate sine, cosine, product, and score values used by the constructions through positions L + 1 are represented exactly. This is possible in the abstract finite-value model because only finitely many offsets and nonzero 31

Published as a conference paper at COLM 2026

values are required, while the regime can retain a separate underflow cell around zero. On (k)

that finite range the ideal identities are evaluated exactly, so Eq. (10) gives Nmax ( g, C, F) ≥ L for every selected k. ■

E

Experiments

We supplement the periodic and conventional non-periodic experiments in §§ 3.5 and 4.4 with additional details. E.1

Languages

We first introduce the different languages we train our transformers on. • ( ab)∗ : the language of strings in which the substring ab is repeated arbitrarily many times. It is star-free, inside LTL[P, MOD] = PFO2 [<, MOD] and outside of PFO2 [<]. It is also the Dyck language (well-balanced parentheses) with 1 pair of parentheses, limited to depth 1. • ( aa)∗ : the language of strings of even length. It is a canonical example of a non-starfree, LTL[P, MOD] language. • aΣ∗ : the language of strings starting with a designated symbol a over some alphabet Σ such that |Σ| > 1. It is the simplest language of the class PFO2 [<] = LTL[P]. • Σ∗ a: the language of strings ending with a designated symbol a over some alphabet Σ such that |Σ| > 1. It belongs in LTL[F] and LTL[Y]. • Σ∗ abΣ∗ : the language of strings containing the contiguous substring ab. It is locally testable and definable in LTL[P, Y]. E.2

Experimental Setup

Our experimental setup follows Delétang et al. (2023); Li & Cotterell (2025). Our transformers use soft attention and strict future masking, with 5 layers, model dimension set to 64, and 8 attention heads. Training strings are of length up to 40, while test strings range from length 41 to 500. The model is trained for 1,000,000 steps with a batch size of 128. For evaluation, we generate 512 samples per test length. Each experiment is run with 5 different random seeds and 3 learning rates (1 × 10−4 , 3 × 10−4 , 5 × 10−4 ). E.3

Periodic-Construction Settings

The periodic experiments in Tab. 2 compare the period-targeting RoPEP and SiPEP variants with NoPE; the conventional fully rotated controls appear in Fig. 2. The component-periodic scheduler is explicitly written out in the code implementation. E.4

Conventional Non-Periodic Settings

Recall in RoPE’s initial presentation that the base value is set to 104 . Prior extrapolation experiments find that this standard choice can be the worst tested base, with improvements on both sides of 104 (Liu et al., 2024). To test whether our conclusions depend on this choice, we therefore sweep bases {10−12 , 10−8 , 10−4 , 1, 104 , 108 , 1012 }. Fig. 3 reports every fully rotated RoPENP configuration and compares it with NoPE. Fig. 2 reports fully rotated RoPENP and SiPENP configurations across the same sweep for ( aa)∗ and ( ab)∗ . E.5

Detailed Results

Tabs. 4 and 5 report the complete aggregate statistics for the tasks and fully rotated settings shown in Figs. 2 and 3. Each row aggregates 5 seeds and 3 learning rates. 32

Published as a conference paper at COLM 2026

Table 4: Detailed results for the fully rotated conventional base sweep on the modular languages in Fig. 2. Language

N∗

PE

Base

Accuracy Max

Mean

Std.

Max

Mean

Std.

( aa)∗ ( aa)∗ ( aa)∗ ( aa)∗ ( aa)∗ ( aa)∗ ( aa)∗

RoPENP RoPENP RoPENP RoPENP RoPENP RoPENP RoPENP

10−12 10−8 10−4 1 104 108 1012

0.522 0.500 0.513 0.509 0.507 0.515 0.517

0.489 0.483 0.501 0.494 0.489 0.490 0.494

0.0204 0.0069 0.0061 0.0076 0.0117 0.0146 0.0095

53.0 65.0 57.0 47.0 48.0 46.0 49.0

41.3 50.1 49.5 34.3 26.3 22.7 23.3

11.6 14.9 3.1 17.2 21.5 21.3 21.9

( aa)∗ ( aa)∗ ( aa)∗ ( aa)∗ ( aa)∗ ( aa)∗ ( aa)∗

SiPENP SiPENP SiPENP SiPENP SiPENP SiPENP SiPENP

10−12 10−8 10−4 1 104 108 1012

0.520 0.654 0.657 0.509 0.522 0.517 0.515

0.504 0.619 0.623 0.496 0.503 0.500 0.497

0.0117 0.0218 0.0273 0.0089 0.0078 0.0049 0.0107

41.0 88.0 90.0 43.0 41.0 0.0 0.0

16.4 71.3 75.7 8.5 2.7 0.0 0.0

20.1 11.9 6.3 16.9 10.2 0.0 0.0

( ab)∗ ( ab)∗ ( ab)∗ ( ab)∗ ( ab)∗ ( ab)∗ ( ab)∗

RoPENP RoPENP RoPENP RoPENP RoPENP RoPENP RoPENP

10−12 10−8 10−4 1 104 108 1012

0.572 0.520 0.530 0.522 0.740 0.817 0.703

0.530 0.510 0.514 0.509 0.560 0.566 0.524

0.0168 0.0057 0.0060 0.0041 0.0602 0.0896 0.0484

98.0 58.0 68.0 56.0 96.0 98.0 72.0

65.1 13.0 48.9 5.2 52.8 5.6 48.1 3.1 66.0 15.7 57.1 14.7 50.1 6.5

( ab)∗ ( ab)∗ ( ab)∗ ( ab)∗ ( ab)∗ ( ab)∗ ( ab)∗

SiPENP SiPENP SiPENP SiPENP SiPENP SiPENP SiPENP

10−12 10−8 10−4 1 104 108 1012

0.515 0.648 0.547 0.515 0.515 0.559 0.586

0.504 0.536 0.523 0.505 0.503 0.514 0.514

0.0050 0.0416 0.0145 0.0045 0.0044 0.0142 0.0204

42.0 54.0 70.0 48.0 46.0 52.0 52.0

16.8 41.9 52.9 23.1 17.1 26.3 24.1

20.6 16.7 7.6 21.6 20.9 21.6 22.8

Table 5: Detailed results for NoPE and the fully rotated conventional RoPE base sweep in Fig. 3. Language

PE

Σ∗ a

Σ∗ a Σ∗ a Σ∗ a Σ∗ a Σ∗ a Σ∗ a Σ∗ a

NoPE RoPENP RoPENP RoPENP RoPENP RoPENP RoPENP RoPENP

aΣ∗ aΣ∗ aΣ∗ aΣ∗ aΣ∗ aΣ∗

NoPE RoPENP RoPENP RoPENP RoPENP RoPENP

Base

N∗

Accuracy Max

Mean

Std.

Max

Mean

Std.

– 10−12 10−8 10−4 1 104 108 1012

0.604 0.741 0.927 0.913 0.753 0.555 0.890 0.685

0.564 0.709 0.829 0.785 0.649 0.524 0.733 0.640

0.0237 0.0181 0.0898 0.0538 0.0483 0.0152 0.1003 0.0305

60.0 149.0 116.0 224.0 82.0 51.0 112.0 70.0

50.8 95.0 81.3 99.8 54.8 45.5 65.7 58.9

3.9 26.6 16.8 46.8 9.2 2.3 14.6 4.8

– 10−12 10−8 10−4 1 104

1.000 1.000 1.000 1.000 1.000 1.000

0.989 0.977 0.927 0.961 0.953 0.847

0.0413 0.0253 0.1033 0.0515 0.1005 0.1449

500.0 500.0 500.0 500.0 500.0 184.0

470.5 82.0 199.5 99.1 166.7 101.4 199.1 95.4 204.9 109.5 146.9 30.2

Continued on next page

33

Published as a conference paper at COLM 2026

Table 5 continued Language

PE

Base

aΣ∗

RoPENP RoPENP

108

Σ∗ abΣ∗ Σ∗ abΣ∗ Σ∗ abΣ∗ Σ∗ abΣ∗ Σ∗ abΣ∗ Σ∗ abΣ∗ Σ∗ abΣ∗ Σ∗ abΣ∗

NoPE RoPENP RoPENP RoPENP RoPENP RoPENP RoPENP RoPENP

aΣ∗

N∗

Accuracy Max

Mean

Std.

Max

Mean

Std.

1012

1.000 1.000

0.928 0.988

0.0864 0.0254

500.0 500.0

293.3 402.9

121.4 125.1

– 10−12 10−8 10−4 1 104 108 1012

0.874 0.770 0.753 0.740 0.647 0.612 0.624 0.658

0.672 0.0829 200.0 0.625 0.0697 103.0 0.604 0.0812 76.0 0.606 0.0556 73.0 0.624 0.0221 51.0 0.572 0.0250 53.0 0.594 0.0183 53.0 0.637 0.0102 50.0

92.9 61.9 58.7 55.2 46.6 49.8 47.2 46.1

32.6 16.8 9.8 7.4 1.5 3.5 2.6 2.2

34

Related documents

• Rope#44728
• Musil’s Imaginary Bridge#775052
• The Theory Of Equations - Unabridged - Illustrated#352449
• Assertion and the semantics of force-markers#735583
• A Double Knot#47106