betaFeedback

WorksComputer Science

A Positional Realizability Theory of Length Generalization in Single-Head Attention

Abstract

Why does length generalization (LG) depend so sharply on the positional encoding (PE)? Relative schemes extrapolate fixed offsets, absolute schemes fix positions, and neither handles growing offsets. We give a realizability theory for a deliberately controlled abstraction, a single positional-only attention head, that derives this well-documented empirical pattern and says precisely where it holds and breaks. The device is a simulation transfer operator TLT_L that re-evaluates a selected length-L0L_0-realizing positional kernel on the longer grid, with a scalar αL∈[0,1]α_L \in [0,1] read off before any training from (Φ,tn)(Φ, t_n) alone. Here αLα_L serves as the computable witness of that taxonomy's derivation, not as a stronger empirical predictor. Our results are a relative-head deep-row characterization for kernels with a strict unique global maximizer (Theorem 2), an absolute/relative duality that derives the pattern (Proposition 4), a learned-absolute underdetermination result, and a static expressivity bound; a sufficiency theorem (Theorem 1) bridges αLα_L to LG, and the general deterministic case is a precise open conjecture (correcting a tempting but invalid "outside-colspan" argument). Experiments confirm the structure: in the controlled single-head regime αLα_L exactly separates the taxonomy's generalizing and non-generalizing (PE, task) cells (2625 trained-model measurements; stable at vocab 64/d=128). Together, these results turn the received PE taxonomy into a positional-kernel transfer theorem, and identify the content and depth mechanisms that escape it. The theory concerns the positional channel alone: tasks whose targets depend on token content, including the standard length-generalization suite such as addition and sorting, fall outside Theorem 2.

Introduction

Length generalization (LG), training on short sequences and testing on longer ones, is a sharp probe of whether a transformer has learned an algorithm rather than a length-specific shortcut, and a practical bottleneck for tasks from arithmetic to long-context reasoning ([1, 11] (Zhou et al. 2024b)). A large body of empirical work has distilled a clear and consistent picture: LG depends acutely on the positional encoding (PE). Learned-absolute PEs typically fail, relative schemes such as RoPE and ALiBi extrapolate fixed relative offsets, absolute schemes lock fixed absolute positions, and growing-offset tasks such as copy and reverse defeat essentially everything ([12, 15, 19, 16, 22]). Existing theory captures pieces of this picture either qualitatively (the RASP-L conjecture, Zhou et al., 2024a; the C-RASP framework, [9]) or through bounds evaluated on the trained model ([10]). **What is missing is an account that derives this picture from the attention mechanism itself: a quantity, computable from the PE and the task before any training, that says which (PE, task) pairs can length-generalize and why.

The quantity, in one example (Figure 1). Fit a single positional attention head to the prev-token target at training length L0L_0: it attends from each position to the one before it. Now re-evaluate the same kernel on a longer grid and count the fraction of new positions whose attention still peaks on the previous token. For RoPE this fraction is 1 (the relative kernel is length-independent); for a copy task, whose target offset grows with the sequence, it is 0. That fraction is the simulation alignment αL∈[0,1]\alpha_L \in[0,1], the object we study. It is read off from the PE’s feature map and the task’s target function alone, with no end-to-end Transformer training, no data samples, and no learned Transformer parameters (only a deterministic kernel-selection on the PE basis). It is the computable witness of a simulation transfer operator TLT_L that re-evaluates the selected length-L0L_0-realizing kernel on the length-LL grid (§4). It is model-free and data-free, but selection-rule dependent: the value depends on which realizing kernel the L0L_0-fit selects (§4).

Overview of the method

Figure 1. Overview of the method. Select (fit) a single positional head’s kernel at length L0L_0 realizing the task’s target pattern RL0R_{L_0}; transfer the same kernel to a longer grid via TLT_L (re-evaluate ΦLWΦLT\Phi_L W \Phi_L^{\mathsf{T}}, no retraining); old rows keep their argmax by the causal-mask identity (Thm 1); score the new rows [L0,L)[L_0,L) to read off αL∈[0,1]\alpha_L \in[0,1]. The whole pipeline uses only (Φ,tn)(\Phi,t_n), with no Transformer training, no data samples, and no learned Transformer parameters (only a deterministic kernel-selection on the PE basis).

Such a pre-training, data-free quantity is useful in two ways. Practically, it lets one triage (PE, task) choices before spending any compute. Scientifically, which is our focus and the more durable contribution, it converts the empirical PE pattern from a list of observations into a derived consequence of what a single attention head can realize and transfer across lengths, with theorems that say exactly where the pattern holds and proofs of where it must break.

We prove that αL=1\alpha_L = 1 implies exact length generalization (Theorem 1), and we characterize precisely when relative encodings reach it (Theorem 2): the required offset must settle on a single value on all but a vanishing fraction of the “deep” rows of the attention grid, and that value must be attainable as a strict maximizer inside the encoding’s own kernel family. So prev/skip-kk generalize while copy and reverse provably cannot (for kernels with a strict unique global maximizer), recovering the received taxonomy as a theorem. Empirically, across 2625 trained-model measurements, αL\alpha_L cleanly separates the (PE, task) pairs that length-generalize from those that do not. We are deliberate about scope: we study a controlled abstraction, the positional channel in isolation, precisely so the theory can be exact. Content and depth escapes are explicitly mapped (§ 6–§ 7); e.g. an induction task length-generalizes through the content channel exactly where positional αL=0\alpha_L=0. We aim to characterize the positional channel’s realizability and to locate where it ceases to be the operative mechanism; explaining all of Transformer LG is outside our scope.

Contributions.

  1. A realizability framework. We cast LG as kernel transfer: a simulation transfer operator TLT_L re-evaluates the selected length-L0L_0-realizing kernel at length LL, and a scalar αL\alpha_L §4 reads off realizability from (Φ,tn)(\Phi,t_n) alone, using no end-to-end Transformer training, no data samples, and no learned Transformer parameters (only a deterministic kernel-selection).

  1. Theory: a characterization of single-head positional LG. The core results are a deep-row characterization for relative heads (Theorem 2: among kernels with a strict unique global maximizer, a relative family transfers a task iff the required offset is constant on a density-one set of deep rows and that offset is attainable within the family, so prev/skip-kk generalize and copy/reverse do not), which subsumes growing-offset impossibility and an absolute/relative duality (Proposition 4) that derives the empirical PE pattern; a learned-absolute underdetermination result (Proposition 2); and a static expressivity bound (Proposition 1). A sufficiency theorem (Theorem 1) is an elementary but essential bridge that makes αL\alpha_L meaningful: what it establishes is that the earlier, already-seen rows keep the same masked attention pattern at longer lengths. Only the general deterministic-PE case remains a precise conjecture (Conjecture 1; we correct a tempting but invalid argument). Several of the formal claims are accompanied by executable checks in the supplement; App. J lists which.

  1. Empirical confirmation and scope. Across 2625 trained-model measurements the theory’s structure holds: αL\alpha_L separates generalizing from non-generalizing (PE, task) cells with AUC = 1.0 (robust to vocab/width). We delineate the boundary precisely (§ 6, § 7): where the content channel carries the target (ALiBi prev, induction) LG occurs without positional realizability, and αL\alpha_L under-predicts low-frequency relative PEs. Tasks whose targets depend on token content, including the standard length-generalization suite such as addition and sorting [12], therefore fall outside Theorem 2. As a practical predictor αL\alpha_L matches but does not beat the coarse taxonomy it explains (we searched for a winning cell and report the negative); its contribution lies in the theory, and we do not frame it as a benchmark comparison.

Organization. § 2 contrasts prior LG theory; § 3–4 set up the abstraction, the operator TLT_L, and αL\alpha_L; § 5 proves the results; § 6 confirms them empirically and maps the boundary where token content identifies the target; § 7 states scope and limitations.

Related Work

Positional encodings for LG. Kazemnejad et al. [12] benchmark PEs and find NoPE competitive; Wang et al. [22] analyze why causal Transformers extrapolate without explicit PEs; ALiBi [15] and RoPE [19] bias attention by relative position; Ruoss et al. [16] boost LG with randomized PEs, and Cho et al. [2] via task-structured position coupling; arithmetic and reasoning benchmarks drive much of this work [1, 11] (Zhou et al. 2024b). These are empirical or architectural; we ask the a priori question of which (PE, task) pairs can extrapolate at all. Theory of LG. RASP-L (Zhou et al., 2024a) conjectures LG holds iff a length-independent RASP program exists, a discrete and qualitative criterion. Izzo et al. [10] prove a simulation sufficiency bound on the required training length, evaluated on trained models, and explicitly leave open the a priori RASP-ranking question. That is exactly our target, which we hit with a continuous PE-computable quantity. Huang et al. [9] give the C-RASP expressibility framework (task-level, PE-class-bound); Golowich et al. [5] tie LG to attention sparsity. Against this line, our Theorem 2 (relative kernels with a strict unique global maximizer cannot length-generalize growing offsets) overlaps the RASP-L/C-RASP intuition that copy/reverse are hard; its novel content is the tie-rule-independent deep-row argument and the capacity corollary (acc⁡train<1\operatorname{acc}_{\mathrm{train}} < 1 under any training-length distribution with unbounded support), neither of which those frameworks state. Spectral views. Gu et al. [6] analyze PE spectra of trained models and prove no impossibility; our TLT_L is a pre-training operator yielding a sufficiency theorem, a relative-encoding necessity theorem, and a (conjectural) general necessary condition. Expressivity, RASP, and circuits. Our impossibility results sit in the lineage of attention expressivity bounds: RASP (Weiss et al., 2021) (which RASP-L and C-RASP build on), the length-dependent self-attention limits of Hahn [8], the constant-depth threshold-circuit view that grounds our static bound [13], and the single-head capacity limits of Sanford et al. [17]; the content/depth escape routes we note are the induction-head and data-routing mechanisms of Olsson et al. [14]; Elhage et al. [4]; Csordás et al. [3]. Implicit bias. αL\alpha_L is computed at the direction a regularized cross-entropy fit realizes [18, 7], which for attention is the token-selection / SVM geometry of Tarzanagh et al. [21]; Theorem 1 is stated for any realizing WW, so it covers this object directly (no min-norm idealization).

Positioning. Table 1 situates αL\alpha_L against the closest prior frameworks. The nearest is C-RASP[Pos] [9], which is also predictive before training; the differences are that it is task-level and binary, tied to specific PE classes, whereas αL\alpha_L is keyed to the PE’s feature map and continuous, computed at the single-attention-head level from (Φ,tn)(\Phi,t_n). We do not claim to answer the a priori question first; C-RASP[Pos] does at the task level. What we add is finer resolution at the level of the PE feature map, a continuous, not a binary verdict witness, and a kernel-transfer operator that yields both the sufficiency theorem and the relative growing-offset necessity theorem (with its tie-rule-independent capacity corollary) in one formalism. Theorem 1’s treatment of the already-seen rows is a single-head specialization of the simulation/transfer idea of Izzo et al. [10] (fit at L0L_0, re-evaluate at LL); the new pieces are the closed-form PE-computable witness αL\alpha_L and the necessity results. Theorem 2 in particular is a relative-head necessity theorem with a deep-row characterization and a tie-rule-independent capacity corollary, which goes beyond the qualitative observation that copy and reverse are hard. We do not claim to be first to observe the empirical pattern; we derive it at the single-head positional level.

pre-training?granularityPE-keyed?direction
RASP-L (Zhou et al., 2024a)yesdiscretenosuff. (conj.)
C-RASP[Pos] [9]yestask, binaryby PE-classsuff. + nec.
Izzo et al. [10]train-length bd.model-levelnosufficiency
spectral PE [6]post-hocmodel-levelspectral–
αL\alpha_L (ours)yescell, cont.by feat. mapsuff. + rel. nec. + conj.

Table 1. Positioning against the closest LG frameworks. αL\alpha_L’s niche: pre-training, keyed to the PE’s feature map, continuous, single-head, with matched sufficiency and relative-head necessity (the general necessary condition is conjectural).

Setup

We follow the single causal attention head abstraction. A token xix_i at position ii has content embedding e(xi)∈Rde(x_i) \in\mathbb{R}^d; the PE supplies a positional feature map φ:N→Rm\varphi: \mathbb{N} \to\mathbb{R}^m. We model the query–key logit as separable,

aij=e(xi)TWc e(xj)+φ(i)TWp φ(j),(1)a_{ij} = e(x_i)^{\mathsf{T}} W_c\,e(x_j) + \varphi(i)^{\mathsf{T}} W_p\,\varphi(j), \tag*{(1)}

with Wc∈Rd×dW_c \in\mathbb{R}^{d \times d}, Wp∈Rm×mW_p \in\mathbb{R}^{m \times m} learnable. We study position-driven tasks: for each query ii at length nn, the head must attend to a task-determined target position tn(i)t_n(i) (e.g. prev-token t=i−1t=i-1; copy t=i−⌈n/2⌉t=i-\lceil n/2\rceil; reverse; attend-first t=0t=0). The required pattern is Rn[i,j]=1[j=tn(i)]R_n[i,j]=\mathbf{1}[j=t_n(i)], causal (j≤ij\le i). Scope hypotheses (S1) single head, one layer, positional-only; (S2) “solve” means correct masked row-argmax with margin >0>0; (S3) content-neutrality on evaluated rows. These are discussed and stress-tested in § 7.

Realizable positional-kernel space. Stacking features Φn∈Rn×m\Phi_n \in\mathbb{R}^{n\times m} (row i=φ(i)Ti=\varphi(i)^{\mathsf{T}}), the head’s realizable positional logits form the linear space Kn:={ΦnWΦnT:W∈Rm×m}\mathcal{K}_n := \{\Phi_n W\Phi_n^{\mathsf{T}} : W \in\mathbb{R}^{m\times m}\}, of dimension rn2r_n^2 with rn=rank⁡(Φn)r_n=\operatorname{rank}(\Phi_n). NoPE has rn=1r_n=1 (constant kernel); learned-absolute has φ(i)\varphi(i) undefined for i≥L0i\ge L_0; sinusoidal/RoPE/ALiBi are deterministic at all lengths, with RoPE/ALiBi depending only on i−ji-j.

The Simulation Transfer Operator and αL\alpha_L

A length-L0L_0-trained head is a parameter W∈Rm×mW \in\mathbb{R}^{m \times m} whose positional kernel realizes the target pattern RL0R_{L_0}. Length generalization asks whether the same WW solves length LL. We therefore define the simulation transfer operator on the head’s parameter WW rather than as a map on kernel blocks. A block map would be ill-defined, since a block ΦL0WΦL0T\Phi_{L_0}W\Phi_{L_0}^{\mathsf{T}} does not determine WW when ΦL0\Phi_{L_0} is rank-deficient (then a nullspace direction NN has ΦL0NΦL0T=0\Phi_{L_0}N\Phi_{L_0}^{\mathsf{T}} = 0 but ΦLNΦLT≠0\Phi_LN\Phi_L^{\mathsf{T}} \ne0, so two heads with the same L0L_0 kernel transfer differently):

TL(W):=ΦLWΦLT(the head’s kernel, re-evaluated on the length-L grid).(2)T_L(W) := \Phi_L W \Phi_L^{\mathsf{T}} \quad\text{(the head’s kernel, re-evaluated on the length-}L\text{ grid).} \tag*{(2)}

A selection rule S\mathcal{S} picks a realizing WSW^{\mathcal{S}} from the L0L_0 fit. We use a regularized cross-entropy fit on the kernel coefficients (400 Adam steps, weight decay 10−410^{-4}), which mirrors how an attention head is trained and respects the PE-specific constraints (RoPE relative kernel, canonical ALiBi recency slope); as the regularization vanishes this direction approaches the max-margin one [18]. The min-norm interpolant W∗=ΦL0+RL0(ΦL0+)TW^* = \Phi_{L_0}^{+}R_{L_0}(\Phi_{L_0}^{+})^{\mathsf{T}} is a different special case. The simulated pattern is PL:=TL(WS)P_L := T_L(W^{\mathcal{S}}), and the simulation alignment is

αL:=1∣SL∣∑i∈SL1[arg max⁡j≤iPL[i,j]=tL(i)]∈[0,1],SL:={query positions of the task}∩[L0,L).(3)\alpha_L := \frac{1}{\lvert S_L\rvert}\sum_{i\in S_L}\mathbf{1}\left[\underset{j \le i}{\operatorname{arg\,max}} P_L[i,j] = t_L(i)\right] \in[0,1], \qquad S_L := \{\text{query positions of the task}\} \cap[L_0,L). \tag*{(3)}

The scored set SLS_L is the task’s own query region restricted to the new rows: all of [L0,L)[L_0,L) for prev/skip-kk and the fixed-position tasks, and the part of the second half that lies beyond L0L_0 for copy and reverse, which is where their targets are defined. We use this one normalization everywhere, including in Theorem 2 and in the implementation; averaging instead over all of [L0,L)[L_0,L) would score rows on which tL(i)t_L(i) does not exist and would change the copy/reverse values by a factor that does not vanish with LL. The argmax in (3) is required to be strict: a row counts as correct only if the target beats every competitor by a positive margin, so an exact tie counts as a failure. This matters for the clamped learned-absolute encoding, whose new-row logits tie exactly (Prop. 4). TLT_L, and hence αL\alpha_L, is thus dependent on which realization is selected: different realizing WW transfer differently, the existence-vs-selection gap we quantify in § 6. The reported αL\alpha_L uses the regularized cross-entropy section (400 Adam steps, weight decay 10−410^{-4}); an ablation (App. § 12) shows it tracks LG with ρ=0.91\rho=0.91 versus ρ=0.56\rho=0.56 for the min-norm interpolant, which is why we adopt it. To be precise about what the computation does and does not involve: the kernel-selection fit (the regularized cross-entropy section above) is a deterministic convex optimization over the PE’s kernel coefficients on the L0L_0 constraint set. It involves no end-to-end Transformer training, no data samples, and no learned Transformer parameters, only Φ\Phi, tnt_n, and the selection rule. We therefore call αL\alpha_L model-free and data-free, but selection-rule dependent, rather than “gradient-free”.

Theory

One question behind the results. The statements below are PE-specific, but they are all instances of a single question. A positional encoding φ\varphi induces a family of realizable kernels K(φ)={φ(i)TWφ(j):W}\mathcal{K}(\varphi) = \{\varphi(i)^{\mathsf{T}}W\varphi(j): W\}, and a task demands, at row ii of length nn, a target key tn(i)t_n(i). Write δn(i)=i−tn(i)\delta_n(i) = i - t_n(i) for the required offset. Then

does K(φ)\mathcal{K}(\varphi) contain a kernel whose masked argmax matches δn(i)\delta_n(i) on all but a vanishing fraction of the new rows, at every length?

Everything that follows answers this for one encoding class at a time. Theorem 1 says a kernel that answers yes at length LL transfers, which is what makes αL\alpha_L meaningful. Theorem 2 answers it for relative families, and the answer has exactly two parts: the demanded offset must settle on a single value δ∗\delta^* on a density-one set of deep rows, and δ∗\delta^* must be attainable as a strict maximizer inside K(φ)\mathcal{K}(\varphi). Prop. 1 shows the affine ALiBi family fails the second part for every interior offset; Prop. 2 shows the learned-absolute family fails it on new rows because those coordinates are untrained; Prop. 3 shows the sinusoidal family satisfies it yet the L0L_0-fit does not select the kernel that does; and Prop. 4 reads off the resulting relative/absolute split.

Conjecture 1 is the general form of the same question, for an arbitrary deterministic φ\varphi, and it is the piece we do not have.

Theorem 1 (Simulation sufficiency, for any realizing WW). Assume (S1)–(S3). Let W∈Rm×mW \in\mathbb{R}^{m \times m} be any positional-kernel parameter such that (i) WW solves length L0L_0 by argmax with margin γ0>0\gamma_0 > 0, and (ii) the alignment computed at WW, αL(W)\alpha_L(W), equals 1 with margin γL>0\gamma_L > 0 on the new rows [L0,L)[L_0,L). Then WW solves the task at length LL with margin min⁡(γ0,γL)\min(\gamma_0,\gamma_L).

Proof. New rows i∈[L0,L)i \in[L_0,L) are correct with margin γL\gamma_L by (ii), since ΦLWΦLT\Phi_L W \Phi_L^{\mathsf{T}} are exactly the logits WW produces at length LL. For old rows i<L0i < L_0, the causal mask restricts competitors to j≤i<L0j \le i < L_0, so the length-LL logits there are identical to the length-L0L_0 logits φ(i)TWφ(j)\varphi(i)^{\mathsf{T}}W\varphi(j) (keys j∈[L0,i]j \in[L_0,i] do not exist when i<L0i < L_0); by (i) those rows are correct with margin γ0\gamma_0. Hence every row is correct.

The proof uses no property of WW beyond (i)–(ii); in particular it does not require the min-norm interpolant. This matters for the experiments: the reported αL\alpha_L is computed at the regularized cross-entropy fit WceW_{\mathrm{ce}}, and Theorem 1 applies verbatim to WceW_{\mathrm{ce}} whenever its αL\alpha_L is 1 – so the theorem certifies the fitted kernel we actually compute. It does not certify the trained transformer, a different object; how often αL(Wmm)=1\alpha_L(W_{\mathrm{mm}})=1 co-occurs with trained-model LG is the empirical question of § 6. Theorem 1 is intentionally elementary: it isolates why the transfer score αL\alpha_L is meaningful, namely that the earlier, already-seen rows keep the same masked attention pattern at longer lengths, and the substantive open question is which (φ,t)(\varphi,t) make the L0L_0-fit reach αL=1\alpha_L=1 (Theorem 2, Prop. 3 answer the negative side).

All three propositions below were obtained under independent adversarial verification (numeric counterexample search + proof audit); we state their corrected cores and record every defect in § 7.

Proposition 1 (Affine features force endpoint argmax). Assume (S1)–(S3) with m=2m = 2, φ(i)=[1,i]T\varphi(i) = [1,i]^{\mathsf{T}}. For every WW and row ii, the logit aij=c0(i)+c1(i)ja_{ij}=c_0(i)+c_1(i)j is affine in the key index jj; hence the unique masked maximizer is the right endpoint j=ij=i if c1(i)>0c_1(i)>0, the left endpoint j=0j=0 if c1(i)<0c_1(i)<0, and a flat tie (margin 0) if c1(i)=0c_1(i)=0. Thus no strict-interior key 0<j<i0<j<i is ever the unique positive-margin argmax, and any interior-target task (e.g. prev-token, i≥2i\ge2) is unrealizable at every length n≥3n\ge3 for any WW.

This is not a strawman: canonical ALiBi’s positional basis is exactly affine in the offset, {1,(i−j)}\{1,(i-j)\} with a sign-constrained slope, so Prop. 1 is why ALiBi-prev has αL=0\alpha_L=0 in our experiments (§ 6) – a single ALiBi head cannot place an interior argmax.

Proof. aija_{ij} affine in j∈{0,…,i}j \in\{0,\ldots,i\} is monotone, so its maximizer is an endpoint, unique unless c1(i)=0c_1(i)=0. An interior target 0<t<i0<t<i would need ait−ai0=tc1(i)>0a_{it}-a_{i0}=t c_1(i)>0 and ait−aii=(t−i)c1(i)>0a_{it}-a_{ii}=(t-i)c_1(i)>0, forcing c1(i)>0c_1(i)>0 and c1(i)<0c_1(i)<0 simultaneously – a contradiction. The competitor set is {0,…,i}\{0,\ldots,i\} at every length, so the conclusion is length-independent.

Proposition 2 (Learned-absolute underdetermination). For learned-absolute PE with φ(i)=vi\varphi(i)=v_i fixed for i<L0i<L_0 and i.i.d. absolutely-continuous for i≥L0i\ge L_0, and any non-degenerate selection rule W=S(v0,…,vL0−1)W=S(v_0,\ldots,v_{L_0-1}) depending on trained rows only, the new-row argmax Mi=arg⁡max⁡j≤iviTWφ(j)M_i=\arg\max_{j\le i}v_i^{\mathsf{T}}W\varphi(j) has a law functionally independent of the new-key labels. Write Ni={L0≤j<i}N_i=\{L_0\le j<i\} for the off-diagonal new keys and k=∣[L0≤j≤i]∣k=|[L_0\le j\le i]|, and assume the row’s target is one of them, tL(i)∈Nit_L(i)\in N_i, with ∣Ni∣=k−1≥1|N_i|=k-1\ge1.

Pr⁡[Mi=tL(i)∣Mi∈Ni]=1k−1,and hencePr⁡[Mi=tL(i)]=Pr⁡[Mi∈Ni]k−1≤1k−1.(4)\Pr[M_i=t_L(i)\mid M_i\in N_i]=\frac{1}{k-1},\qquad\text{and hence}\qquad\Pr[M_i=t_L(i)]=\frac{\Pr[M_i\in N_i]}{k-1}\le\frac{1}{k-1}. \tag*{(4)}

Extrapolation is therefore at or below chance on such rows: the selection rule carries no information about which untrained key is the target. The hypothesis tL(i)∈Nit_L(i)\in N_i is what makes the statement about the untrained coordinates; it holds for the moving targets of prev and skip-k once i≥L0+ki\ge L_0+k, which is the case the proposition is used for.

Proof sketch. For new keys g(j)=Wvjg(j)=Wv_j depends only on the independent vjv_j; the map vi↦arg⁡max⁡jviTg(j)v_i\mapsto\arg\max_j v_i^{\mathsf{T}}g(j) is a fixed function in which the label tL(i)t_L(i) never appears, and SS (trained-rows only) cannot encode it. Conditioned on WW, the off-diagonal g(j)g(j), j∈Nij\in N_i, are i.i.d. and independent of viv_i, so their indices are exchangeable and the argmax is uniform on NiN_i given that the maximum is attained there, which is (4). We assume as a hypothesis that the maximizer MiM_i is almost surely unique. This does not follow from W≠0W \ne0, nor from WW merely being injective on the compared keys: for an antisymmetric WW with Wv0=0Wv_0 = 0 one has viTWvi=viTWv0=0v_i^{\mathsf{T}}Wv_i = v_i^{\mathsf{T}}Wv_0 = 0 identically, so the self-key and the trained key 0 tie for every viv_i (App. § 9).

Why both hypotheses are needed. The probability in (4) is conditional because the trained (old) keys and the self-key j=ij = i are not exchangeable with the new keys: the self-key contributes the quadratic viTWviv_i^{\mathsf{T}}Wv_i, so the global maximum need not lie in NiN_i at all. Monte-Carlo confirms both parts: at L=30L = 30 the conditional hit rate is 0.115 against 1/(k−1)=0.1111/(k - 1) = 0.111, while the unconditional rate is 0.034 because the winner lands in NiN_i only 30% of the time; at L=60L = 60 the figures are 0.025 / 0.026 / 0.016 with 65% (experiments/verify_prop2_conditional.py). The unconditional hit rate is therefore at or below chance. The hypothesis tL(i)∈Nit_L(i) \in N_i is equally necessary: if the target is an old key (as in attend-first, where tL(i)=0t_L(i) = 0), the trained keys are precisely the ones the L0L_0-fit has shaped, and the hit probability can exceed 1/(k−1)1/(k - 1). With a min-norm WW fitted on the trained rows we measure Pr⁡[Mi=0]\Pr[M_i = 0] at up to 5.2×5.2\times the bound (feature dimension m=64m = 64, L=128L = 128; the ratio grows with mm and LL and is below 1 for small mm; experiments/verify_prop2_hypothesis.py). That regime is governed by Prop. 4 instead. Finally, a degenerate selection such as W=0W = 0 makes every logit equal, which is why almost-sure uniqueness needs non-degeneracy. This is underdetermination rather than an empty constraint cone: a rescuing WW realizing the target on new rows exists with positive probability (≈20\approx20–35% in Monte-Carlo); the inductive-bias rule is simply blind to the untrained coordinates and cannot select it.

Proposition 3 (Sinusoidal: a realizing kernel exists but is not selected). For sinusoidal absolute PE with incommensurate frequencies: (A) for any fixed offset δ\delta a WW realizing it exists at all lengths (the multi-frequency kernel has a unique global max at d=δd = \delta, disambiguated arbitrarily far beyond the lowest-frequency period); (B) for growing offsets (copy/reverse), no translation-invariant kernel with a strict unique global maximizer tracks a length-dependent offset (Theorem 2), so αL→0\alpha_L \to0; empirically the fitted kernel gives αL≈0\alpha_L \approx0 at every length we test.

The qualifier in (B) is necessary, and the sinusoidal family itself shows why. A translation-invariant kernel that is monotone increasing over the accessible offset range has no interior maximizer, and the causal window then hands it the largest available offset for free. Within the sinusoidal span with the standard 16 frequencies and base 10410^4, the single component κ(d)=sin⁡(dθmin⁡)\kappa(d) = \sin(d\theta_{\min}) with θmin⁡≈1.78⋅10−4\theta_{\min} \approx1.78 \cdot10^{-4} is increasing for d≲8833d \lesssim8833; at L=17665L = 17665 the demanded copy offset is exactly 8833 and this kernel attains αL=1\alpha_L = 1. This is far outside the lengths we study (our sinusoidal experiments reach L=128L = 128, where the kernel is nowhere near its turning point), but it shows the impossibility must be stated for kernels with a global peak, not for translation invariance alone. In plain terms: sinusoidal PEs are not impossible in principle for a fixed offset since a realizing kernel exists at every length. What fails is selection: the training-length fit does not pick that kernel. We are therefore not claiming “sinusoidal fixed-offset cannot generalize”; we are isolating where it does and does not. Existence ≠\ne selection. The transfer operator’s L0L_0-fit W∗W^* does not recover the fixed-offset rescue: sinusoidal prev decays (αL=0.45\alpha_L = 0.45 at L=60L=60, 0.34 at L=128L=128). The common intuition that a sinusoidal encoding must fail once the required offset exceeds its lowest-frequency period is thus false; the correct statement is conditional, and the sub-unit transferred accuracy is exactly αL\alpha_L measuring the existence-vs-selection gap.

We now give a genuine necessity theorem for the most important failure case – growing offsets under relative encodings – which explains the αL=0\alpha_L=0 copy/reverse cells of RoPE/ALiBi.

Theorem 2 (Relative-head deep-row characterization). Assume (S1)–(S3). Let SLS_L denote the scored rows (the task’s query positions in [L0,L)[L_0,L)), so that αL\alpha_L is the fraction of SLS_L on which the masked argmax hits the target; we use this one normalization throughout, matching the implementation. Fix a relative (translation-invariant) family K\mathcal{K} of kernels aij=κ(i−j)a_{ij} = \kappa(i-j), and consider those κ∈K\kappa\in\mathcal{K} that admit a strict unique global maximizer c(κ)=arg⁡max⁡d≥0κ(d)c(\kappa) = \arg\max_{d \ge0}\kappa(d), under a fixed tie rule. (A constant kernel has no strict maximizer, so NoPE, whose family is spanned by the constant, is excluded.) Call a scored row deep if i≥c(κ)i \ge c(\kappa); the remaining scored rows form a set H(κ)⊆[L0,c(κ))\mathcal{H}(\kappa) \subseteq[L_0,c(\kappa)) of size at most c(κ)−L0c(\kappa)-L_0, a bound independent of LL. Assume the scored set grows, ∣SL∣→∞|S_L| \to\infty, and write K+\mathcal{K}_+ for the kernels in K\mathcal{K} that realize the task at L0L_0 with positive margin, which is the hypothesis Theorem 1 needs in order to turn αL\alpha_L into length generalization.

Then some κ∈K0\kappa\in\mathcal{K}_0 with a strict unique global maximizer achieves αL→1\alpha_L \to1 if and only if there is an offset δ∗\delta^* with

(i) density:

#{i∈SL:δL(i)≠δ∗}#SL→L→∞0,\frac{\#\{i \in S_L : \delta_L(i) \ne\delta^*\}}{\#S_L} \xrightarrow{L\to\infty} 0,

(ii) attainability: δ∗=c(κ)\delta^* = c(\kappa) for some κ∈K0\kappa\in\mathcal{K}_0. (5)

For a given κ\kappa, αL→1\alpha_L \to1 iff (5)(i) holds with δ∗=c(κ)\delta^* = c(\kappa). Both hypotheses are needed. Attainability must be inside K0\mathcal{K}_0 rather than K\mathcal{K}: a kernel peaked at the new rows’ offset but failing at L0L_0 has αL→1\alpha_L \to1 without solving the task at either length, so the existential quantifier alone would not deliver length generalization. And the proof compares ∣H(κ)∣|\mathcal{H}(\kappa)| against ∣SL∣|S_L|, which is informative only when the scored set grows. The exact conclusion αL=1\alpha_L = 1 requires more than (5): the realized offset must hit the target on every scored row, including the finitely many rows in H(κ)\mathcal{H}(\kappa), where the causal window clips the argmax below c(κ)c(\kappa). Consequently fixed-relative-offset tasks (prev, skip-kk) are realizable by any family containing a kernel whose global maximizer is at kk, while growing-offset (copy) and within-length-varying (reverse) tasks are not: αL→0\alpha_L \to0 for every κ∈K\kappa\in\mathcal{K} with a strict unique global maximizer.

Proof sketch (full proof, both tie rules, App. § 9). Deep-row constancy of the realized offset: for a deep row i≥c(κ)i \ge c(\kappa) the causal window [0,i][0,i] contains c(κ)c(\kappa), and c(κ)c(\kappa) maximizes κ\kappa over all offsets d≥0d \ge0, hence over the window; so the masked argmax offset equals the constant c(κ)c(\kappa), independent of nn. (This is why the maximizer must be global: a merely local peak could be beaten by a larger offset that the window admits at long lengths.) A κ\kappa therefore hits a deep row iff c(κ)c(\kappa) equals that row’s required offset, so

αL=#{i∈SL, i≥c(κ):δL(i)=c(κ)}+r(κ)#SL,0≤r(κ)≤∣H(κ)∣,\alpha_L = \frac{\#\{i \in S_L,\, i \ge c(\kappa) : \delta_L(i) = c(\kappa)\} + r(\kappa)} {\#S_L}, \qquad0 \le r(\kappa) \le|\mathcal{H}(\kappa)|,
(6)(6)

where r(κ)r(\kappa) counts the finitely many clipped rows that happen to be correct. (⇐\Leftarrow) Given (i), take κ\kappa with c(κ)=δ∗c(\kappa) = \delta^*. By (6) the deep rows it misses are exactly those with δL(i)≠δ∗\delta_L(i) \ne\delta^*, a vanishing fraction by (i), and ∣H(κ)∣/#SL→0|\mathcal{H}(\kappa)|/\#S_L \to0 since H(κ)\mathcal{H}(\kappa) is fixed while #SL→∞\#S_L \to\infty. Hence αL→1\alpha_L \to1. (⇒\Rightarrow) Suppose αL→1\alpha_L \to1 for such a κ\kappa. Put δ∗:=c(κ)\delta^* := c(\kappa), attainable by construction, giving (ii); by (6) the fraction of scored rows with δL(i)≠δ∗\delta_L(i) \ne\delta^* is 1−αL+o(1)→01-\alpha_L+o(1) \to0, giving (i). For the corollaries, no δ∗\delta^* satisfies (i) when the offset grows (copy, δL=⌈L/2⌉\delta_L = \lceil L/2 \rceil: for L>2c(κ)L > 2c(\kappa) every copy row is deep with realized offset c(κ)c(\kappa), so the missed fraction tends to 11) or varies within a length with positive density (reverse: a nested-window monotonicity argument forces failure already at L0L_0).

The hypotheses are each necessary, and the scope of the characterization is discussed with counterexamples in App. § 9.§ 6.

Proposition 4 (Absolute/relative duality). Assume (S1)–(S3). (a) Relative side. A translation-invariant family containing a kernel whose strict unique global maximizer is at kk length-generalizes the fixed relative offset kk (prev/skip-kk: αL=1\alpha_L=1 at all lengths). On a fixed absolute position the demand offset i−ti-t grows with the row, so by Theorem 2 no kernel with a strict unique global maximizer attains αL→1\alpha_L \to1; and empirically the kernel the L0L_0-fit selects decays, αL=0.80,0.40,0.20,0.12,0.055,0.039\alpha_L = 0.80, 0.40, 0.20, 0.12, 0.055, 0.039 at L=30,40,60,128,256,512L = 30, 40, 60, 128, 256, 512 for RoPE on attend-first. (b) Absolute side, for the clamped learned-absolute encoding used in our experiments. Let φ(i)=vmin⁡(i,L0−1)\varphi(i) = v_{\min(i,L_0-1)}, so all positions i≥L0i \ge L_0 share one feature. Such a head length-generalizes a fixed absolute position in the trained range (αL=1\alpha_L=1 at all lengths, with an LL-independent margin), and fails on a fixed relative offset: every new key carries the same feature, so the logits over j≥L0j \ge L_0 tie exactly and the target cannot be singled out (αL=0\alpha_L=0 with margin 00). For the i.i.d.-extended variant the corresponding statement is probabilistic and is Prop. 2. (c) Neither generalizes a growing offset (copy/reverse), again for kernels with a strict unique global maximizer. Empirically (App. § 9): attend-first clamped-absolute 1.00/relative 0.00; prev clamped-absolute 0.00 (an exact tie)/relative 1.00. The i.i.d.-extended variant instead scores at the chance level of Prop. 2 (≈0.05\approx0.05 in our Monte-Carlo), as it should: the two objects fail for different reasons.

Which “absolute” object. Stating part (b) for “an absolute kernel” without qualification would conflate three distinct objects. (1) An unrestricted absolute kernel K[i,j]K[i,j], with a free entry for every pair, is not limited to absolute targets at all: setting K[i,i−1]K[i,i-1] large and the rest small encodes the sub-diagonal directly, so it realizes prev-token at every length. (2) A learned-absolute table extended by i.i.d. unseen rows is at chance on new rows (Prop. 2). (3) The clamped learned-absolute implementation used in our experiments collapses all positions i≥L0i \ge L_0 onto one feature, so distinct new rows become indistinguishable and a moving target cannot be resolved. The duality claim is about (2) and (3), the objects a trained model actually has, and part (b) above now says so. The same care applies on the relative side: sinusoidal absolute features can represent translation-invariant fixed-offset kernels, as Prop. 3 itself shows, so “absolute features” and “absolute-only behaviour” are not the same thing. What separates the regimes is the realizable kernel family a given encoding induces, which is exactly the quantity condition (5)(ii) makes explicit.

Offset taxonomy diagram

Figure 2. The offset taxonomy, derived (Theorem 2, Prop. 4). A relative kernel length-generalizes a fixed relative offset; a clamped learned-absolute encoding does the reverse; and neither handles a growing offset (the shared blind spot, right column). Throughout, the relative statements are for kernels with a strict unique global maximizer, the hypothesis of Theorem 2; the accompanying text explains why it is needed and what the L0L_0-fit contributes. This 2 × 3 verdict is exactly the empirical PE taxonomy, here a consequence of what a single positional head can realize.

Existence versus selection on the relative side. It is tempting to say that a relative kernel simply cannot reach a fixed absolute position because that would need a peak at the growing offset ii. That reasoning is wrong, because the causal window truncates at d=id = i: a monotone increasing κ\kappa, e.g. κ(d)=d\kappa(d) = d, puts the masked argmax at j=0j = 0 on every row at every length, so it realizes attend-first exactly. Such a kernel has no strict unique global maximizer, which is why Theorem 2 does not cover it, and its realizable analogue is present in genuine PE families: within the RoPE span, sin⁡(dθmin⁡)\sin(d\theta_{\min}) is increasing over the whole range of lengths we study. What rules this out in practice is not translation invariance but two other things: the canonical ALiBi slope is sign-constrained to be non-positive (dropping that constraint does let an ALiBi-form kernel solve attend-first, while leaving prev-token unrealizable as Prop. 1 requires), and the L0L_0-fit does not select the monotone solution, so the transferred accuracy decays with LL as reported in part (a). This is the same existence-versus-selection distinction we draw for sinusoidal encodings in Prop. 3, and it applies here too.

Conjecture 1 (General length-generalization impossibility). For a deterministic PE defined at all lengths, if RLnew∉ΠKLR_L^{\mathrm{new}} \notin\Pi_{K_L} and a quantitative separation holds – for every WW realizing RL0R_{L_0} with old-row margin ≥γ\ge\gamma, the residual (I−ΠKL)RLnew(I-\Pi_{K_L})R_L^{\mathrm{new}} forces max⁡j≤i,j≠tφ(i)TWφ(j)≥φ(i)TWφ(tL(i))\max_{j \le i,j \ne t}\varphi(i)^{\mathsf T}W\varphi(j) \ge\varphi(i)^{\mathsf T}W\varphi(t_L(i)) on some new row ii – then no single head solves both L0L_0 and LL.

Remark (why the colspan argument is insufficient). One might conclude impossibility from “φ(i)∉colspan⁡(ΦL0)\varphi(i) \notin\operatorname{colspan}(\Phi_{L_0})”. That does not suffice: the components of WW acting on the orthogonal complement are unconstrained by the L0L_0 fit and permit a rescuing WW as easily as a failing one. The argmax flip is the substance of the statement and requires proof; we leave it open.

Partial progress (App. § 9; the conjecture stays open). We can say more. (i) A saturation lemma. For a finite-dimensional deterministic PE with ΦL0\Phi_{L_0} of full column rank mm, the map W↦ΦL0WΦL0TW \mapsto\Phi_{L_0}W\Phi_{L_0}^{\mathsf{T}} is injective (σmin⁡=σmin⁡(ΦL0)2\sigma_{\min} = \sigma_{\min}(\Phi_{L_0})^2), so a given kernel block determines WW and hence PLP_L. (ii) But this does not decide LGLG, because “solving at L0L_0” (S2) is an argmax+margin cone of WW, not a single block: distinct blocks with identical L0L_0 argmax transfer to opposite LL-verdicts. LGLG is decidable only relative to a declared selection rule (e.g. min-norm), not from “the L0L_0 fit” alone – the existence-vs-selection gap again. (iii) The obstruction is not cone-emptiness: an LP witness shows a single WW solving both L0L_0 and LL for prev-token sinusoidal in the under-determined regime (rank =12≪m=48= 12 \ll m = 48), so CL0∩CL≠∅C_{L_0} \cap C_L \ne\emptyset; the failure mechanism is selection (Prop. 2) rather than an empty cone. (iv) Sinusoidal escapes the saturation route entirely: at realistic frequency counts ΦL0\Phi_{L_0} is rank-deficient or wildly ill-conditioned (cond⁡∼104\operatorname{cond} \sim10^{4}–101110^{11}), so WW is never robustly pinned. The sharpest remaining open sub-case: a deterministic PE with a non-empty joint cone on a non-realizable growing-offset target and selection failure.

Empirical confirmation of the theory

We test whether trained transformers obey the realizability structure the theory predicts. These experiments are meant to confirm the theorems rather than to benchmark a predictor: αL\alpha_L is the theory’s computable witness, and the relative/absolute taxonomy it should track is precisely the empirical pattern the theory derives (Prop. 4).

What is certified vs. what is measured. The theory certifies a fitted positional kernel: αL\alpha_L is a property of (Φ,tn)(\Phi,t_n), and Theorem 1 guarantees that a kernel that realizes the task at L0L_0 with positive margin and reaches αL=1\alpha_L=1 with positive margin on the new rows still solves the task at length LL; both premises are required. The trained Transformer is a separate object, a non-convex optimizer over both positional and content channels. These experiments test the empirical bridge: whether certified positional realizability (αL→1\alpha_L \to1) co-occurs with the trained model’s length generalization. A gap between them is therefore expected and informative. It is exactly the selection/content/depth boundary of § 7, and does not contradict the theory.

Protocol. Tiny decoder-only transformers (vocab 12, d=64d = 64) trained at variable length up to L0=20L_0 = 20 and evaluated on extrapolation rows [L0,L)[L_0, L). Three depth tiers: the 1-layer 1-head setting the theory describes (1-layer, 1-head) and two scale/escape tiers (2-layer 4-head, 4-layer 4-head). Tasks span bounded-offset (prev, skip-kk), growing-offset (copy, reverse), and absolute (first) targets, across five PEs (learned-abs, NoPE, ALiBi, sinusoidal, RoPE); 2625 measurements (3 × 5 × 7 × 5 × 5) over 5 seeds and 5 test lengths. Where we report correlations on a learnable subset (train acc >0.8> 0.8), it is because LGLG of a task a model never learned at L0L_0 is undefined; we always give the unconditioned numbers too. The tasks are position-dependent (small vocabulary, repeated tokens) so that content cannot localize the target position. This statistically discourages content shortcuts but does not make the trained model’s content logit literally argmax-neutral as (S3) assumes (the value/content path remains). So these experiments confirm the positional theory within its assumed scope; they do not confirm it independently of (S3). Where content genuinely carries the target the impossibility results are vacuous, which is exactly the boundary we map in § 7 and App. § 16.

The evaluation grid. The taxonomy these experiments test is derived (Prop. 4), so the axes follow the theory’s own categories. Table 2 lists every condition we evaluate together with the reason for each level. The task set covers all three offset regimes (fixed-relative, fixed-absolute, growing), and the PE set is the five canonical classes rather than a subset.

AxisLevelsRationale
PEslearned-abs, NoPE, ALiBi, sinusoidal, RoPEthe five canonical PE classes
Tasksprev, skip-2/3/5, copy, reverse, firstfixed-relative, growing-offset, fixed-absolute regimes
(+ pos-2/5, App. E)interior absolute positions, off the causal boundary
Lengths30, 40, 50, 60, 80extrapolation beyond L0=20L_0=20 (1.5×–4×)
Seeds0, 1, 2, 3, 4variance / bootstrap CIs
Models1L1H, 2L4H, 4L4H1-layer 1-head setting + depth/multi-head escape routes

Table 2. The evaluation grid. Each axis follows the theory’s categories or standard practice; the reason given for each level is the reason it was included.

Primary confirmation: αL\alpha_L separates generalizing from non-generalizing cells. Over all 35 (PE, task) cells (no learnability filter), cell-level αL\alpha_L separates the 6 that length-generalize (LG ≥0.5\ge0.5) from the 29 that do not with AUC = 1.00 (base rate 0.17; permutation p=5×10−5p=5\times10^{-5}, 20k shuffles). This is not a fragile 1.0: the margin is wide (min αL\alpha_L among positives = 1.00 vs. max among negatives = 0.36), and restricting to the 11 non-trivial cells (dropping negatives with αL≈0\alpha_L\approx0) keeps AUC = 1.0. The screen is thus validated on the hard cells too (all 20 NoPE/ALiBi/copy/reverse cells sit at αL≈0\alpha_L\approx0, std 0.02, and none generalize in this single-head regime). As a graded (rank) statistic over the same 35 cells the unconditioned Spearman is modest (ρ=0.47\rho=0.47), because the signal is dominantly the clean binary separation; we report it for transparency and turn to the learnable subset for the graded view.

αL\alpha_L acts primarily as a binary realizability indicator. On the learnable subset (train acc >0.8>0.8, which retains 15 of 35 cells; all NoPE, ALiBi, and copy/reverse are excluded, so this subset can only probe the bounded/absolute regime), a naive cell-level ρ=0.90\rho=0.90 (bootstrap 95% CI [0.73, 0.95], 15 cells, 5 seeds). But this is almost entirely the binary 0-vs-1 separation re-expressed (all numbers cell-level): binarizing αL\alpha_L at 0.5 already gives ρ=0.85\rho=0.85, and restricting to non-trivial cells (αL>0.05\alpha_L>0.05) gives ρ=0.77\rho=0.77. On the only family with genuinely interior αL\alpha_L values (sinusoidal bounded-offset) there is no positive graded signal: ρ=−0.20\rho=-0.20 at the cell level (n=4n=4 cells) and ≈0\approx0 at finer aggregations (0.04 row-level, 0.09 at (PE,task, LL)). We therefore do not claim αL\alpha_L is a graded predictor; it is a binary realizability indicator, which is what the theory predicts. (The unconditioned cell-level Spearman over all 35 cells is 0.47.)

Sufficiency is approximate, with characterized violations. The “≥\geq 92%-precision sufficient screen” claim must be qualified. The precision of αL≥τ⇒LG≥0.7\alpha_L\geq\tau\Rightarrow\mathrm{LG}\geq0.7 rises with τ\tau: 0.925 at τ=0.5\tau=0.5, 0.95 at τ=0.7\tau=0.7, 0.987 at τ=0.9\tau=0.9. At τ=0.5\tau=0.5 there are 12 violating rows out of 160, and they come from three families: rope-first at L=30L=30 (αL=0.80\alpha_L=0.80, LG = 0.13, all 5 seeds), sinusoidal-prev at L=40L=40 (αL=0.50\alpha_L=0.50, LG = 0.14, all 5 seeds), and sinusoidal-first at L=60L=60, αL=1.0\alpha_L=1.0, one seed each, the worst being LG = 0.49 against a 5-seed cell mean of 0.77). These are the existence-vs-selection gap of Prop. 3 surfacing in the validated predictor: the CE fit over-sharpens αL\alpha_L at small LL where the true selected kernel decays. We therefore do not claim a clean row-level sufficient indicator; we claim a strong binary screen (AUC 1.0) with a positive cell-level association on the learnable subset, with violations confined to the relative/sinusoidal selection gap.

Relation to the received taxonomy. A PE-blind rule (“is the offset bounded?”) attains negative correlation (ρ=−0.24\rho=-0.24), so PE-awareness is essential. The hand-built taxonomy baseline (relative-PE×bounded V absolute-PE×absolute-task) reaches ρ=0.85\rho=0.85, within our bootstrap CI: αL\alpha_L matches but does not beat it. In the theory framing this is the expected outcome rather than a shortfall: that taxonomy is exactly the coarse rule Proposition 4 derives, so αL\alpha_L tracking it confirms the theory. The role of αL\alpha_L is to be the directly computed witness of why the taxonomy holds and where it breaks (the boundary where token content identifies the target below); it is not offered as a way to beat a baseline. We attempted to find a PE the taxonomy cannot classify but αL\alpha_L can (a low-frequency RoPE, still “relative”): the attempt instead exposed an αL\alpha_L false negative: on the content-neutral skip-k task the trained model generalizes a target the linear-kernel fit deems unrealizable. Since the task is content-neutral this is not a content rescue in the sense of App. H; we have not isolated the mechanism further and report it as an unexplained disagreement between the trained model and the fitted kernel, and as a negative result for the comparison with the taxonomy.

What the theorem certifies vs. what we measure. Theorem 1 (any realizing WW) certifies the fitted kernel WW at which we compute αL\alpha_L. It does not certify the trained transformer, which is a different parameter. So αL(Wfit)=1\alpha_L(W_{\mathrm{fit}})=1 guarantees the fitted kernel solves length LL; whether the trained model does is the empirical question, and the two can diverge: rope-first (αL=0.80\alpha_L=0.80, LG 0.13 at L=30L=30) and sinusoidal-first (αL=1.0\alpha_L=1.0 at L=80L=80, LG 0.77 on average and as low as 0.49 on the worst seed) are cases where Wtrained≠WfitW_{\mathrm{trained}} \ne W_{\mathrm{fit}}. We therefore do not claim “the certified object is the validated one.” The right test of the theorem’s relevance is co-occurrence of αL(Wfit)=1\alpha_L(W_{\mathrm{fit}})=1 with trained-model LG, which holds for ≥92%\ge92\% of high-αL\alpha_L rows (rising to 98% at αL≥0.9\alpha_L\ge0.9); this is strong but not exact. Theorem 1 covers any realizing kernel, so the cross-entropy fit we use is also certified as the min-norm interpolant; the two simply differ in how well they predict the trained model, at ρ=0.91\rho=0.91 against ρ=0.56\rho=0.56 (App. § 12). We therefore frame the empirical link as a co-occurrence rate rather than a theorem.

Scale and depth (H3): one-sidedness. At 2- and 4-layer/4-head, the graded rank correlation on learnable cells falls from 0.90 to ρ=0.31\rho=0.31 and 0.28, with bootstrap CIs that include 0 (Table 4), so beyond depth 1 αL\alpha_L is no longer a significant graded predictor. What does survive at depth is the sufficient-screen property: precision rises to 0.94 and 0.97 (CIs [0.89, 0.97], [0.94, 0.99]), i.e. high αL\alpha_L still implies LG (Table 4, Figure 6). The lost graded signal is entirely attributable to low-αL\alpha_L cells that generalize via mechanisms outside the positional-only abstraction: ALiBi and NoPE realize prev-token and first through the content/recency channel (αL\alpha_L=0, LG = 1.0; Table 3, bottom), and the set of such cells grows with depth. This is the predicted (S3) boundary: αL\alpha_L is a sufficient indicator rather than a necessary one, mirroring exactly that sufficiency (Theorem 1) and the relative growing-offset necessity (Theorem 2) are proven while the fully general necessity (Conjecture 1) is open. The heatmaps in Figure 5 localize where content rescues position.

PEtaskαL\alpha_LLG (1L1H)LG (2L4H)
RoPEskip51.001.00±0.000.97±0.02
RoPEprev1.000.87±0.050.85±0.13
RoPEcopy0.000.10±0.010.14±0.01
sinusoidalfirst1.000.87±0.130.92±0.04
sinusoidalskip30.250.22±0.030.11±0.01
learned-absfirst1.001.00±0.001.00±0.00
learned-absprev0.000.08±0.000.08±0.00
Content-channel cases (S3 violations): αL\alpha_L under-predicts at scale
ALiBiprev0.000.18±0.001.00±0.00
ALiBifirst0.000.15±0.011.00±0.00
NoPEfirst0.000.16±0.011.00±0.00

Table 3. Training-free αL\alpha_L (at L=60L=60) vs. empirical LG accuracy (mean over 5 seeds), 1-layer 1-head and scale (2L4H) tiers. Top: αL\alpha_L tracks 1L1H LG. Bottom: at scale, the content/recency channel (outside the positional-only abstraction, S3) lets ALiBi/NoPE generalize where αL=0\alpha_L=0, making the predictor’s one-sidedness visible.

Figure 5. Training-free α60\alpha_{60} (left) and empirical LG@60 (right) over (PE, task), 1L1H. Agreement is strong in this single-head regime; the content-driven disagreements (which emerge at depth, not shown here) are characterized in § 7.

tierdepthlearnable Spearman ρ\rho (95% CI)sufficiency precision (95% CI)
1L1H10.90 [0.73, 0.95]0.925 [0.88, 0.96]
2L4H20.31 [−0.16, 0.76]0.94 [0.89, 0.97]
4L4H40.28 [−0.15, 0.66]0.97 [0.94, 0.99]

Table 4. Depth trend (H3), learnable cells (train acc > 0.8), 5 seeds.

Figure 6. H3: learnable-cell Spearman ρ(αL,LG)\rho(\alpha_L, \mathrm{LG}) (circles) drops with depth (its bootstrap CI includes 0 at depths 2, 4), while sufficiency precision (squares) stays ≥0.92\geq0.92 with tight CIs. αL\alpha_L remains a sufficient screen at all depths.

Figure 4. Empirical LG (solid) and training-free αL\alpha_L (dashed) vs. test length LL (train L0L_0=20), 1L1H. αL\alpha_L tracks both who generalizes and how LG decays with LL.

Limitations

App. § 10 sets out, with evidence, the five ways αL\alpha_L departs from a trained model’s behaviour: a selection gap, content rescue, a depth escape, low-frequency under-prediction, and overprediction when the trained model selects a different kernel. The first four are failures of necessity and leave the sufficiency direction intact, which is why we call αL\alpha_L a one-sided screen; the fifth is the one case where high αL\alpha_L does not co-occur with length generalization.

The remaining scope limits: (1) Single head / single layer. Multi-head and depth provably escape the impossibility (an anchor head plus a content-match head solves copy at depth 1); all impossibility claims are scoped to the positional-only subclass. (2) Content channel. Where content carries the target, αL\alpha_{L} under-predicts; this is the binding limitation and the source of the indicator’s one-sidedness. We show it is closable (App. H): on a content-driven induction task, positional αL=0\alpha_{L}=0 for every PE yet a 2-layer ALiBi model reaches LG 0.84, and a content-aware αL+\alpha_{L}^{+} flags the regime αL\alpha_{L} misses (with residual PE-modulation left to future work). (3) The forward question is open. Theorem 1 (stated for any realizing WW) certifies that αL(W)=1⇒LG\alpha_{L}(W)=1 \Rightarrow\mathrm{LG}, but it does not say which (φ,t)(\varphi,t) admit a fitted WW reaching αL=1\alpha_{L}=1; we characterize the negative side (Theorems 2, Proposition 3) but a positive forward criterion is open.

A list of statements we explicitly do not claim, with the reason for each, is given in App. B.1.

Conclusion

We gave a realizability theory of length generalization for single-head positional attention: a simulation transfer operator and its scalar witness αL\alpha_{L}, a sufficiency theorem, and a deep-row characterization for relative heads (for kernels with a strict unique global maximizer, αL→1\alpha_{L}\to1 exactly when the offset is constant on a density-one set of deep rows and that offset is attainable within the encoding’s kernel family) that subsumes growing-offset impossibility and the absolute/relative duality deriving the empirical pattern, alongside a learned-absolute characterization; only the general deterministic-PE case remains conjectural. Selected theoretical claims are accompanied by executable checks that probe their assumptions. Experiments confirm the structure: in the controlled single-head regime αL\alpha_{L} exactly separates the taxonomy’s generalizing and non-generalizing cells (AUC = 1.0). They also locate the theory’s boundary: the content channel, outside the abstraction, can carry the target where positional realizability cannot (ALiBi prev, induction), and αL\alpha_{L} under-predicts low-frequency relative PEs. Rather than replacing the received taxonomy, αL\alpha_{L} derives it from positional-kernel transfer and exposes its escape routes. Extending the theory across the content channel and to multi-head/depth, which provably escape the single-head impossibilities, is the natural next step.

Acknowledgments

We thank the Action Editor, Zhanxing Zhu, and the three anonymous reviewers. Their careful reading identified errors in earlier versions of Theorem 2 and Propositions 2 and 4, and their comments substantially improved both the results and the presentation.

Use of language models

Large language models (Claude and Codex) were used extensively in preparing this work: to draft and edit the text, to write the experiment, analysis and verification code, and to develop and check the mathematical arguments, including searches for counterexamples to the stated results. The authors take full responsibility for the content. Every reported number can be reproduced from the released code and data.

Full proofs

Theorem 1 (Simulation sufficiency, any realizing WW)

Theorem 1 (Simulation sufficiency, any realizing WW). Fix any WW satisfying (i)–(ii). Under (S1)–(S3) the row-ii logits at any length nn are aij(n)=φ(i)⊤Wφ(j)a_{ij}^{(n)}=\varphi(i)^\top W\varphi(j) for j≤ij\le i, with the content term argmax-neutral. New rows i∈[L0,L)i\in[L_0,L): by (ii) the simulated PL[i,⋅]=ai(L)P_L[i,\cdot]=a_i^{(L)} has its unique masked maximum at tL(i)t_L(i) with gap ≥γL\ge\gamma_L. Old rows i<L0i<L_0: the causal mask restricts the key set to {0,…,i}⊆{0,…,L0−1}\{0,\ldots,i\}\subseteq\{0,\ldots,L_0-1\}, and for those jj the features φ(j)\varphi(j) are exactly those present at length L0L_0; hence aij(L)=aij(L0)a_{ij}^{(L)}=a_{ij}^{(L_0)} entrywise, so the masked argmax and gap ≥γ0\ge\gamma_0 are inherited verbatim from (i). Every row’s unique masked maximizer is tL(i)t_L(i) with gap ≥min⁡(γ0,γL)>0\ge\min(\gamma_0,\gamma_L)>0.

Remark (why not the min-norm interpolant). Stating this for the min-norm W∗W^* would invoke ΦL0W∗ΦL0⊤=RL0\Phi_{L_0}W^*\Phi_{L_0}^{\top}=R_{L_0}, which is false unless RL0∈KL0R_{L_0}\in K_{L_0}. The argument needs no such exactness and no choice of WW: only that the chosen WW is argmax-correct at L0L_0 and has αL(W)=1\alpha_L(W)=1. Hence it covers the fitted WW used in the experiments, though not the trained transformer. The theorem’s force comes entirely from the invariance of the already-seen rows under the causal mask; the new-row clause restates (ii).

Proposition 1 (Affine features force endpoint argmax)

Proposition 1 (Affine features force endpoint argmax). With φ(i)=[1,i]⊤\varphi(i)=[1,i]^\top write W=(W00W01W10W11)W=\begin{pmatrix}W_{00}&W_{01}\\W_{10}&W_{11}\end{pmatrix}. Then aij=φ(i)⊤Wφ(j)=c0(i)+c1(i)ja_{ij}=\varphi(i)^\top W\varphi(j)=c_0(i)+c_1(i)j with c0(i)=W00+iW10c_0(i)=W_{00}+iW_{10}, c1(i)=W01+iW11c_1(i)=W_{01}+iW_{11}, which is affine in the key index j∈{0,…,i}j\in\{0,\ldots,i\}. An affine function on a finite integer chain is monotone, so its maximizers are endpoints, and the maximizer is unique unless c1(i)=0c_1(i)=0 (a flat row, margin 00, excluded by (S2)). For a strict interior target 0<t<i0<t<i, optimality would require ait≥ai0a_{it}\ge a_{i0} and ait≥aiia_{it}\ge a_{ii}, i.e. tc1(i)≥0tc_1(i)\ge0 and (t−i)c1(i)≥0(t-i)c_1(i)\ge0; with t>0t>0, t−i<0t-i<0 this forces c1(i)≥0c_1(i)\ge0 and c1(i)≤0c_1(i)\le0, hence c1(i)=0c_1(i)=0 and a zero margin. Therefore no interior key is ever the unique, positive-margin maximizer. Since the competitor set {0,…,i}\{0,\ldots,i\} does not depend on nn, the conclusion holds at every length; prev-token (t=i−1t=i-1, interior for i≥2i\ge2) is thus unrealizable for all n≥3n\ge3.

Caveat. The statement is about the unique positive-margin argmax, not the set inclusion argmax ⊆{0,i}\subseteq\{0,i\}, which fails on the measure-zero locus c1(i)=0c_1(i)=0 (there the argmax set is the whole chain).

Proposition 2 (Learned-absolute underdetermination)

Let φ(i)=vi\varphi(i)=v_i with v0,…,vL0−1v_0,\ldots,v_{L_0-1} fixed and vL0,…,vL−1∼μv_{L_0},\ldots,v_{L-1}\sim\mu i.i.d. from an absolutely continuous isotropic law, and W=S(v0,…,vL0−1)W=S(v_0,\ldots,v_{L_0-1}) any rule of the trained rows only (so W⊥{vj}j≥L0W\perp\{v_j\}_{j\ge L_0}. Put g(j)=Wφ(j)g(j)=W\varphi(j). Uniqueness: for two keys j≠j′j\ne j' with j,j′≠ij,j'\ne i the difference aij−aij′=vi⊤W(vj−vj′)a_{ij}-a_{ij'}=v_i^\top W(v_j-v_{j'}) is affine in the absolutely continuous viv_i, and is nonzero for genuine functional dependence precisely when W(vj−vj′)≠0W(v_j-v_{j'})\ne0; a comparison against the self-key contributes vi⊤Wvj−vi⊤Wviv_i^\top Wv_j-v_i^\top Wv_i, which is a polynomial of degree two in viv_i rather than an affine functional. For pairs of distinct non-self keys the coefficient W(vj−vj′)W(v_j-v_{j'}) is nonzero whenever WW does not collapse them, and the zero set of a nonzero affine functional is null. Comparisons involving the self-key are not covered by this argument, and no condition of that kind suffices: take WW antisymmetric with Wv0=0Wv_0=0. Then vi⊤Wvi=0v_i^\top Wv_i=0 because WW is antisymmetric, and vi⊤Wv0=0v_i^\top Wv_0=0 because Wv0=0Wv_0=0, so the self-key and the trained key 00 carry identical logits for every viv_i, while Wvj≠WviWv_j\ne Wv_i still holds generically. With positive probability the remaining logits are all smaller and this identical pair is the maximum. We therefore take almost-sure uniqueness of MiM_i as an explicit hypothesis of the proposition rather than deriving it; it holds, for instance, whenever the realized logit vector has distinct entries almost surely, which we verify numerically for the fitted kernels we use. Target-independence: the map vi↦arg max⁡jviTg(j)v_i \mapsto\operatorname{arg\,max}_j v_i^\mathsf{T}g(j) is a fixed measurable function of (vi,{g(j)})(v_i,\{g(j)\}) in which the label tL(i)t_L(i) never appears, and SS cannot encode it into the new-key geometry; thus Law⁡(Mi)\operatorname{Law}(M_i) does not reference tL(i)t_L(i). Chance rate: conditioned on WW, the off-diagonal new keys {g(j):L0≤j<i}={Wvj}\{g(j): L_0 \leq j < i\} = \{Wv_j\} are i.i.d. and independent of viv_i, so by exchangeability their indices are equally likely to carry the maximum given that the maximum is attained in NiN_i. With tL(i)∈Nit_L(i) \in N_i and k=∣{L0≤j≤i}∣k = |\{L_0 \leq j \leq i\}| this gives Pr⁡[Mi=tL(i)∣Mi∈Ni]=1/(k−1)\Pr[M_i = t_L(i) \mid M_i \in N_i] = 1/(k-1), and since {Mi=tL(i)}⊆{Mi∈Ni}\{M_i = t_L(i)\} \subseteq\{M_i \in N_i\}, the chain rule gives Pr⁡[Mi=tL(i)]=Pr⁡[Mi∈Ni]/(k−1)≤1/(k−1)\Pr[M_i = t_L(i)] = \Pr[M_i \in N_i]/(k-1) \leq1/(k-1). The old keys and the self-key are not exchangeable with NiN_i, so they may hold the maximum; that is why the unconditional value is the smaller one. □

Underdetermination, not cone-emptiness. A rescuing WW realizing the target on all new rows exists with positive probability (Monte Carlo: ≈20\approx20–35%35\% of draws; experiments/theorem2b_learned_abs_montecarlo.py); the selection rule is simply blind to the untrained coordinates. The self-key j=ij=i is excluded because aii=viTWvia_{ii}=v_i^\mathsf{T}Wv_i is a quadratic (non-exchangeable) form with mean tr⁡W\operatorname{tr}W, which is why the conditional rate is 1/(k−1)1/(k-1) rather than 1/k1/k.

Proposition 3 (Sinusoidal: existence vs. selection)

(A) Existence. With incommensurate geometric frequencies {θk}\{\theta_k\}, the translation-invariant kernel g(d)=∑kcos⁡(θk(d−δ))≤#{θk}g(d)=\sum_k \cos(\theta_k(d-\delta)) \leq\#\{\theta_k\} with equality iff θk(d−δ)∈2πZ\theta_k(d-\delta)\in2\pi\mathbb{Z} for all kk; incommensurability forces d=δd=\delta, so gg has a unique global maximum at the target offset for any fixed δ\delta (verified numerically to δ≈5×104\delta\approx5 \times10^4, far beyond the lowest-frequency period, refuting the intuition that a sinusoidal encoding must fail once the offset exceeds that period). Hence a WW realizing a fixed offset exists at all lengths. (B) Growing offsets. A translation-invariant kernel with a strict unique global maximizer c(κ)c(\kappa) realizes the constant offset c(κ)c(\kappa) on every deep row (Theorem 2), which can equal δL=⌈L/2⌉\delta_L=\lceil L/2\rceil only at L∈{2c(κ)−1,2c(κ)}L\in\{2c(\kappa)-1,2c(\kappa)\}, and at some L≤c(κ)L\leq c(\kappa) where the window clips onto a lower local peak; for every L>2c(κ)L>2c(\kappa) each scored row is missed, so αL→0\alpha_L\to0 on copy/reverse. (The earlier “cannot hold at two lengths” phrasing was imprecise: shallow clipping does let one kernel solve copy at two particular lengths, e.g. κ[10]=5,κ[30]=8\kappa[10]=5,\kappa[30]=8 at L0=20L_0=20 and L=60L=60; the correct statement is asymptotic. Without a global maximizer the conclusion fails outright, as the monotone example after the proposition shows.) Existence ≠\ne selection: the L0L_0-fit W∗W^* does not recover the fixed-offset rescue — under the transfer operator sinusoidal prev decays (αL=0.45\alpha_L=0.45 at L=60L=60, 0.340.34 at L=128L=128), and the sub-unit value is αL\alpha_L quantifying the selection gap. □

Theorem 2 (Relative-head deep-row characterization)

Let aij=κ(i−j)a_{ij}=\kappa(i-j) on causal keys j≤ij\leq i, with a strict unique global maximizer c(κ)=arg max⁡d≥0κ(d)c(\kappa)=\operatorname{arg\,max}_{d\geq0}\kappa(d), under a fixed tie rule. Write SLS_L for the scored rows (the task’s query positions in [L0,L)[L_0,L)), which is the set αL\alpha_L averages over. Deep-row constancy (Lemma). For any row i≥c(κ)i\geq c(\kappa) the window [0,i][0,i] contains c(κ)c(\kappa), and no admitted offset beats it because c(κ)c(\kappa) is the maximum over all d≥0d\geq0; so the masked argmax offset is the constant c(κ)c(\kappa) for all such ii and all nn (verified over 4000 random kernels, both tie rules; globality is what makes this work for the unbounded-support RoPE and ALiBi families).

By the Lemma, κ\kappa hits a deep scored row if δL(i)=c(κ)\delta_L(i)=c(\kappa), so with H(κ)=SL∩[L0,c(κ))\mathcal{H}(\kappa)=S_L\cap[L_0,c(\kappa)), whose size is at most c(κ)−L0c(\kappa)-L_0 uniformly in LL (it is empty once the query region starts above c(κ)c(\kappa), as happens for copy and reverse),

αL=#{i∈SL, i≥c(κ):δL(i)=c(κ)}+r(κ)#SL,0≤r(κ)≤∣H(κ)∣,(5)\alpha_L = \frac{\#\{i\in S_L,\ i\geq c(\kappa):\delta_L(i)=c(\kappa)\}+r(\kappa)} {\#S_L}, \qquad0\leq r(\kappa)\leq|\mathcal{H}(\kappa)|, \tag*{(5)}

so the clipped rows contribute O(1/#SL)→0O(1/\#S_L)\to0. Note that both the theorem and (5) normalize by #SL\#S_L; this is the same convention as the implementation, and it matters, since for tasks whose query region is a strict subset of [L0,L)[L_0,L) (copy, reverse) the two would differ by a non-vanishing factor.

(⇐)(\Leftarrow) Assume (5): the required offset equals δ∗\delta^* off a density-zero subset of SLS_L, and some κ∈K0\kappa\in\mathcal{K}_0 has c(κ)=δ∗c(\kappa)=\delta^*. Take that κ\kappa. Old rows are correct because κ\kappa realizes the task at L0L_0, and the causal-mask identity of Thm 1 preserves that correctness at length LL; by (5) the missed deep rows form a vanishing fraction and ∣H(κ)∣|\mathcal{H}(\kappa)| is fixed, so αL→1\alpha_L \to1. (Verified for δ∗∈{1,2,3,5,8}\delta^{*} \in\{1,2,3,5,8\}, LL up to 5000.) Note both hypotheses are needed: for the canonical ALiBi family κ(d)=c0+sd\kappa(d) = c_0 + sd, s≤0s \le0, the maximizer is c(κ)=0c(\kappa) = 0 for every admissible slope, so no ALiBi kernel realizes δ∗≥1\delta^{*} \ge1 however constant the demanded offset is.

The exact conclusion αL=1\alpha_L = 1 needs every scored row, not just the deep ones. The clipped set H(κ)\mathcal{H}(\kappa) never leaves SLS_L, so if a row in it is missed, αL<1\alpha_L < 1 at every LL. Example: κ(d)=−∣d−30∣\kappa(d) = -|d - 30| with L0=20L_0 = 20 leaves the ten rows [20,30)[20,30) clipped; a task demanding offset 1 there and 30 on deep rows satisfies exact constancy on all deep rows, yet αL=1−10/(L−20)\alpha_L = 1 - 10/(L - 20), i.e. 0.500, 0.875, 0.990, 0.99995 at L=40,100,103,2⋅105L = 40, 100, 10^3, 2 \cdot10^5: it tends to 1 but never equals it. Hence αL=1\alpha_L = 1 is equivalent to the realized offset hitting the target on every scored row, deep and clipped alike.

(⇒)(\Rightarrow) Suppose αL→1\alpha_L \to1 for some κ∈K0\kappa\in\mathcal{K}_0. Put δ∗=c(κ)\delta^{*} = c(\kappa), which is attainable in K0\mathcal{K}_0 by construction, giving (5)(ii). By (5) the fraction of scored rows with δL(i)≠δ∗\delta_L(i) \ne\delta^{*} equals 1−αL+o(1)→01 - \alpha_L + o(1) \to0, giving (5)(i). For the corollaries, no δ∗\delta^{*} can satisfy (5)(i) in either of two cases. (a) The offset grows with nn (copy, δn=⌈n/2⌉\delta_n = \lceil n/2 \rceil): for all L>2c(κ)L > 2c(\kappa) every copy row is deep with realized offset c(κ)c(\kappa), which cannot equal ⌈L/2⌉→∞\lceil L/2 \rceil\to\infty, so the failing fraction tends to 1 and αL→0\alpha_L \to0. (b) It varies within a length (reverse, δn(i)=2i−2⌈n/2⌉+1\delta_n(i) = 2i - 2\lceil n/2 \rceil+ 1, distinct offsets {1,3,5,…}\{1,3,5,\ldots\}): a nested-window monotonicity argument gives a contradiction already at L0=20L_0 = 20. Row 18 demands offset 17 and its window is {0,…,18}\{0,\ldots,18\}, which contains offset 15, so κ[17]>κ[15]\kappa[17] > \kappa[15]. Row 17 demands offset 15 and its window {0,…,17}\{0,\ldots,17\} contains offset 17, so κ[15]>κ[17]\kappa[15] > \kappa[17]. The two are incompatible, independent of c(κ)c(\kappa). A 20k-kernel sweep confirms no κ\kappa solves reverse at L0L_0 (iff_constant_offset_lg.py).

Why density and not exact constancy. See App. § 9.§ 6 for the counterexample that forces condition (5)(i) to be stated in density.

Why deep-row/asymptotic, not a finite-LL “complete iff”. One might hope to add the necessity clause “shallow rows = min⁡(i,δ∗)\min(i,\delta^{*})”, but it is false: κ=[1.46,1.96,1.80,6.32]\kappa= [1.46, 1.96, 1.80, 6.32] (offsets 0–3, c(κ)=3c(\kappa) = 3) makes deep rows take offset 3 but shallow row i=2i=2 argmax offset 1≠min⁡(2,3)=21 \ne\min(2,3)=2 (window values [1.46,1.96,1.80][1.46, 1.96, 1.80]). Shallow rows are a finite, κ\kappa-dependent set, uncharacterized by a universal formula but immaterial to αL\alpha_L as L→∞L \to\infty—hence the criterion is on deep rows. Two further cautions: the growing-offset clash is asymptotic rather than two-length (κ[10]=5,κ[30]=8\kappa[10]=5,\kappa[30]=8 solves copy at both L0=20L_0=20 and L=60L=60 via shallow clipping); and “bounded offset” is insufficient (the ii-parity offset δ(i)∈{1,2}\delta(i) \in\{1,2\} scores exactly 0.5, 20k-kernel sweep). Capacity corollary: for a training-length distribution with unbounded support, every fixed kernel with a strict unique global maximizer incurs positive error on copy, so acc⁡<1\operatorname{acc} < 1. The restriction matters: a kernel peaked at cc solves copy at L∈{2c−1,2c}L \in\{2c-1,2c\}, so a distribution supported on those two lengths alone can be solved exactly.

Theorem 2: necessity of the hypotheses, and scope

Why each hypothesis is needed. (a) The condition is asymptotic. Requiring δL(i)=δ∗\delta_L(i) = \delta^{*} on every deep row would be too strong: αL\alpha_L only measures a fraction, so a density-zero exceptional set is compatible with αL→1\alpha_L \to1. Concretely, let δL(i)=2\delta_L(i) = 2 when ii is a perfect square and 1 otherwise. A kernel peaked at offset 1 fails exactly on the squares, so 1−αL=O(L−1/2)→01 - \alpha_L = O(L^{-1/2}) \to0 even though the offset is not eventually constant (αL=0.944,0.987,0.996\alpha_L = 0.944, 0.987, 0.996 at L=200,5⋅103,5⋅104L = 200, 5 \cdot10^3, 5 \cdot10^4). (b) Attainability inside the family. Constancy alone is not sufficient: δ∗\delta^{*} must be attainable in K0\mathcal{K}_0, and one cannot simply exhibit κ(d)=−∣d−δ∗∣\kappa(d) = -|d - \delta^{*}| without checking that it belongs to the PE-induced family. Canonical ALiBi is exactly this case: its family κ(d)=c0+sd\kappa(d) = c_0 + sd with s≤0s \le0 has its maximizer at offset 0 for every admissible slope, so no ALiBi kernel peaks at δ∗=1\delta^{*}=1 and ALiBi cannot realize prev-token positionally, consistent with Prop. 1. Condition (5)(ii) makes this explicit. (c) The existence of a global maximizer is load-bearing. Translation invariance alone does not forbid tracking a growing offset, because the causal window admits ever larger offsets as LL grows. Take the unbounded ladder κ(d)=−1\kappa(d) = -1 except κ(20⋅4m)=m+2\kappa(20 \cdot4^m) = m + 2 for m=0,1,2,…m = 0,1,2,\ldots; its values increase without bound, so it has no maximizer at all, and it attains αL=1\alpha_L = 1 on copy along the whole sequence L=40,160,640,2560,10240,40960L = 40, 160, 640, 2560, 10240, 40960 (we verified this numerically). A kernel that does have a strict unique global maximizer c(κ)c(\kappa) can also solve copy at particular lengths, namely at L∈{2c(κ)−1,2c(κ)}L \in\{2c(\kappa)-1,2c(\kappa)\}, where the demanded offset ⌈L/2⌉\lceil L/2\rceil equals c(κ)c(\kappa), and possibly at some L≤c(κ)L \le c(\kappa) where the causal window clips the argmax onto a lower local peak (for κ\kappa peaked at 100 with a secondary peak at 20 we find αL=1\alpha_L = 1 at L=39,40,199,200L = 39,40,199,200), but it fails for every L>2c(κ)L > 2c(\kappa), which is the content of the corollary. The impossibility is asymptotic; finitely many lucky lengths are not a counterexample to it. Growing-offset impossibility is therefore a statement about kernels with a global peak, and we state it with that qualifier throughout. (d) Deep rows are defined by c(κ)c(\kappa) alone. One might also ask for i≥Di \ge D for a support radius DD, but that would be vacuous for the very families we care about, since RoPE and ALiBi kernels have unbounded support, so D=∞D = \infty and no row would be deep. Globality of the maximizer is what the argument actually needs, and with it the clipped set is H(κ)⊆[L0,c(κ))\mathcal{H}(\kappa) \subseteq[L_0,c(\kappa)). Scope of the characterization. The criterion is on deep rows and the asymptotic αL\alpha_L; we do not claim a finite-LL “complete iff” that also pins shallow rows to min⁡(i,δ∗)\min(i,\delta^*) – that is false: the kernel κ=[1.46,1.96,1.80,6.32]\kappa= [1.46,1.96,1.80,6.32] (peak at offset 3) makes shallow row i=2i=2 select offset 1, not min⁡(2,3)=2\min(2,3)=2 (we reproduce this in App. § 9). Shallow rows are a finite, κ\kappa-dependent set that does not affect the asymptotic αL\alpha_L. Two further cautions: the growing-offset clash is asymptotic (a kernel peaked at offset 30 solves copy at both L0=20L_0=20 and L=60L=60 via shallow clipping – there is no two-length contradiction); and “bounded offset” is insufficient. The last point is now exactly condition (5)(i): an ii-parity offset alternating in {1,2}\{1,2\} is bounded, but each value occurs with density 1/21/2, so no δ∗\delta^* has a vanishing exceptional fraction and αL\alpha_L sits at 0.5. What matters is that one offset occurs with density one; boundedness alone is not enough. This theorem subsumes the growing-offset impossibility and the absolute/relative duality. Capacity corollary: for a training-length distribution with unbounded support, every fixed kernel with a strict unique global maximizer incurs positive error on copy, so acctrain<1\mathrm{acc}_{\mathrm{train}} < 1. The restriction matters: a kernel peaked at cc solves copy at L∈{2c−1,2c}L \in\{2c-1,2c\}, so a distribution supported on those two lengths alone can be solved exactly. We additionally stress-tested the corrected statement numerically, fuzzing both the kernel (4000 random kernels under both tie rules, in iff_constant_offset_lg.py) and the task’s offset function (constant, perfect-square, power-of-two and cube exceptional sets, parity, drifting and block-alternating offsets, and growing offsets), confirming that αL→1\alpha_L \to1 tracks density-1 constancy and nothing weaker (experiments/verify_thm2_density.py); the proof does not rely on these checks.

Proposition 4 (Absolute/relative duality)

Relative κ(i−j)\kappa(i-j): a fixed offset kk is realized by a κ\kappa whose strict unique global maximizer is d=kd=k, correct on every row at every length (αL=1\alpha_L=1). Attend-first (t=0t=0) demands the growing offset ii, so by Theorem 2 no κ\kappa with a strict unique global maximizer reaches αL→1\alpha_L \to1. This is the right qualifier: a monotone increasing kernel such as κ(d)=d\kappa(d)=d has no global maximizer and does realize attend-first at every length (the causal window truncates at d=id=i), so what defeats attend-first in practice is the sign constraint on the canonical ALiBi slope together with the L0L_0-fit’s failure to select such a kernel, not translation invariance by itself; the selected RoPE kernel decays as αL=0.80,0.40,0.20,0.12,0.055,0.039\alpha_L=0.80,0.40,0.20,0.12,0.055,0.039 at L=30,40,60,128,256,512L=30,40,60,128,256,512. Clamped learned-absolute φ(i)\varphi(i): attend-first is realized by the length-independent column-0-hot kernel (margin +1+1 at all lengths). A fixed relative offset moves the target across absolute positions into the collapsed range, where all keys j≥L0j \ge L_0 share one feature and their logits tie exactly, so αL=0\alpha_L=0 with margin 0. For the i.i.d.-extended variant the corresponding statement is the chance bound of Prop. 2. Growing offsets defeat both. Verified for the clamped object in src/spectra.py (attend-first 1.00; prev 0.00 with margin exactly 0) and for the i.i.d.-extended object in experiments/duality_abs_vs_rel.py (prev 0.046, the chance level of Prop. 2). In duality_abs_vs_rel.py the relative side scores 0.00 on attend-first and 1.00 on prev; the concrete PEs behave as their own families dictate, so RoPE scores 0.80 on attend-first at L=30L=30 and decays with LL (Prop. 4(a)), while ALiBi scores 0.00 on prev (Prop. 1). Note that duality_abs_vs_rel.py’s attend-first “absolute” construction is the unrestricted kernel K[i,j]=1[j=0]K[i,j]=1[j=0], i.e. object (1) above, which is why it is reported separately from the clamped values.

Failure modes of αL\alpha_L

Failure modes of αL\alpha_L. We list the five ways αL\alpha_L departs from a trained model’s length generalization. They are the precise boundary of the single-head positional theory, and each is something we observe and characterize.

  1. Selection gap. A rescuing kernel WW exists, but the L0L_0-fit does not select it, so αL<1\alpha_L < 1 despite realizability in principle (sinusoidal fixed-offset: αL=0.45\alpha_L=0.45 at L=60L=60; Prop. 3). Existence ≠\ne selection.

  1. Content rescue. The target is carried by the content channel, outside the abstraction, so the positional αL\alpha_L under-predicts: LG occurs with αL=0\alpha_L=0 (induction, and ALiBi/NoPE prev/first at depth; Appendix § 16). This is the binding limitation (S3).

  1. Depth / multi-head escape. Multiple heads or layers route around the single-head impossibility (an anchor head + a content-match head solves copy at depth 1), so αL\alpha_L can under-predict at scale while remaining a sufficient screen (§ 6).

  1. Low-frequency relative under-prediction. Even within the positional channel and on a content-neutral task, αL\alpha_L is not a perfect graded predictor: on content-neutral skip-kk a frequency-scaled (low-frequency) RoPE model generalizes a target the linear-kernel fit deems unrealizable (Table 10, Appendix § 17), so αL\alpha_L under-predicts it. The task is content-neutral, so the discrepancy is not content rescue in the sense of (2); we have not isolated the mechanism further, and we report it as an unexplained case where the trained model generalizes and the fitted kernel does not.

RoPE freq. scaleαL\alpha_Ltrain accLG@60
1.0 / 0.31.001.001.00
0.11.000.940.93
0.030.000.880.88
0.010.000.230.18

Table 10. RoPE frequency sweep on content-neutral skip-3 (1L1H). No discriminating cell: where the model generalizes the taxonomy is right; at scale 0.03 αL\alpha_L under-predicts (false negative); at 0.01 the model cannot learn at all.

  1. Overprediction by the fitted kernel. The converse also occurs: the fitted kernel can have high αL\alpha_L while the trained model selects a different solution and fails to generalize (rope-first at L=30L=30, αL=0.80\alpha_L=0.80 against LG 0.13; sinusoidal-first at L=80L=80 on one seed). Theorem 1 is unaffected, since it is a statement about a single realizing kernel; what fails is the empirical bridge from αL(Wfit)\alpha_L(W_{\mathrm{fit}}) to the behaviour of WtrainedW_{\mathrm{trained}}.

The five are distinct: (1) is intra-positional selection, (2) is a different channel, (3) is a larger architecture, (4) is a graded-versus-binary gap, and (5) is a mismatch between the fitted and the trained kernel. The first four leave the sufficiency direction (αL→1⇒\alpha_L \to1 \Rightarrow LG) intact and are failures of necessity, which is why we call αL\alpha_L a one-sided screen; (5) is the one case where high αL\alpha_L does not co-occur with length generalization, which is why we report the empirical link as a co-occurrence rate.

Scope of the individual statements

The following limits attach to specific results and are easy to over-read. (i) No general sinusoidal LG impossibility: Conjecture 1 is open and the intuition that a sinusoidal encoding must fail once the required offset exceeds its lowest-frequency period is refuted (Prop. 3). (ii) Sinusoidal fixed-offset transfer is not exact: existence of a rescuing WW does not imply its selection by the L0L_0-fit. (iii) The learned-absolute rate 1/(k−1)1/(k-1) is conditional on the argmax falling among the off-diagonal new keys, and applies when the target is one of them; the self-key is a non-exchangeable quadratic competitor, which is why it is 1/(k−1)1/(k-1) and not 1/k1/k, and the unconditional rate is smaller. (iv) Prop. 1 is about the unique positive-margin argmax; set-containment is a different statement (which fails on the measure-zero tie locus). (v) All impossibility results are single-head, positional-only; multi-head/depth/content provably route around them. (vi) Prop. 2 proves chance via i.i.d. random untrained features, whereas our learned-absolute implementation clamps φ(i)=emin⁡(i,L0−1)\varphi(i)=e_{\min(i,L_0-1)} (matching the trained model); both routes give chance, by exchangeability and by degeneracy respectively, but they are distinct mechanisms and we do not conflate them.

Experimental details

Architecture. Decoder-only transformer, dmodel=64d_{\mathrm{model}}=64, GELU MLP (width 4d4d), pre-LN, learned token embedding (vocab 12). PEs: NoPE; sinusoidal (additive); learned-absolute (table of size L0L_0, positions ≥L0\ge L_0 clamped to L0−1L_0-1); RoPE (rotary on q,kq,k); ALiBi (fixed geometric slopes). Tiers: 1-layer/1-head, 2-layer/4-head, 4-layer/4-head. Training. AdamW (lr 3×10−4\mathrm{lr}\ 3 \times10^{-4}, wd 0.01), batch 64, 2000 steps, variable train length n∼Unif⁡[L0/2,L0]n \sim\operatorname{Unif}[L_0/2,L_0], L0=20L_0=20, cross-entropy over query positions (ignore-index elsewhere). Tasks (target position tn(i)t_n(i), all position-dependent via small vocab): prev (i−1i-1), skip-kk (i−ki-k, k∈{2,3,5}k \in\{2,3,5\}), copy (i−⌈n/2⌉i-\lceil n/2\rceil), reverse, first (0). Evaluation. Accuracy on extrapolation query rows [L0,L)[L_0,L) at L∈{30,40,50,60,80}L \in\{30,40,50,60,80\}, 5 seeds. Predictor fit. Cross-entropy fit of the kernel coefficients to the L0L_0 targets (400 Adam steps), PE-structural constraints imposed (RoPE relative basis; ALiBi recency slope constrained ≤0\le0); strict-unique-argmax scoring on new rows. Compute. Apple M3 Pro (MPS); the full 2625-measurement, 5-seed study runs in ∼\sim55 min.

Additional results

Table 4 reports the depth trend (H3) over all three tiers; Figure 6 plots it. As depth grows (1→2→41 \to2 \to4 layers), the learnable-cell graded rank correlation drops from 0.90 (CI [0.73, 0.95]) to 0.31 and 0.28 with bootstrap CIs that include 0 (Table 4); the precision on high-αL\alpha_L rows instead stays high and tight (0.925 →\to 0.94 →\to 0.97). The lost graded signal is explained by the content channel: the set of low-αL\alpha_L cells that nonetheless generalize grows with depth. Scoring cells by their means, it is {ALiBi prev/first/skip2, NoPE prev/first, RoPE first} at 2 layers and gains ALiBi skip3 at 4 layers, with the two marginal members strengthening as depth grows (NoPE prev 0.53 →\to 0.74, RoPE first 0.83 →\to 1.00). Depth does not break the sufficient-indicator property; it adds more content-channel routes around a low positional αL\alpha_L, exactly the (S3) boundary.

Table 4: Depth trend (H3), learnable cells (train acc > 0.8), 5 seeds. The Spearman column is cell-level with a bootstrap 95% CI over the (PE, task) cells; the precision column is the rate Pr[LG ≥\geq 0.7 | αL≥\alpha_L \geq 0.5] with a bootstrap 95% CI over the high-αL\alpha_L rows. αL\alpha_L stays a high-precision sufficient indicator at every depth (precision CIs well above chance); the graded rank correlation, by contrast, is significant only at depth 1 – at depths 2, 4 its CI includes 0, consistent with αL\alpha_L acting as a binary screen rather than a graded predictor once content rescues low-αL\alpha_L cells.

Inductive-bias ablation (which fit drives the correlation). Table 5 computes αL\alpha_L three ways on the 75 1L1H (PE,task, LL) rows and correlates each with empirical LG. The min-norm interpolant of Theorem 1 yields only ρ=0.56\rho=0.56; the regularized cross-entropy fit used throughout yields 0.91, and its weight-decay→0\to0 limit, which approaches the max-margin direction (Soudry et al., [18]), yields 0.92. The predictive content of αL\alpha_L therefore comes from the cross-entropy direction rather than from the min-norm object, a gap we state here.

kernel fitSpearman ρ\rhoPearson
min-norm interpolant (Thm 1’s W∗W^*)0.560.57
cross-entropy, wd=10−410^{-4} (reported αL\alpha_L)0.910.95
cross-entropy, wd→0\to0 (max-margin)0.920.94

Table 5. Inductive-bias ablation (75 rows in the 1L1H setting). The cross-entropy fit, not the min-norm interpolant, drives the αL\alpha_L–LGL_G correlation.

Robustness checks. The learnability cutoff is inert: cell-level ρ=0.91/0.90/0.90\rho=0.91/0.90/0.90 at train >{0.5,0.7,0.9}> \{0.5, 0.7, 0.9\} (train accuracy is bimodal). On the 20 dropped cells αL\alpha_L has std 0.02 (uniformly ≈0\approx0), so it provides no rank signal there by construction. Scale robustness (vocab 64, d=128d=128) is reported in App. § 14; training-length robustness (the screen AUC stays 1.0 and the per-cell verdicts are unchanged at L0∈{10,20,40}L_0 \in\{10, 20, 40\}) in App. § 15; and PE frequency/θ\theta-base/dimension robustness in App. § 17. Interior fixed-absolute positions, which remove the reliance on the special boundary position 0, are in App. § 13.

Interior fixed-absolute positions

The fixed-absolute regime in the main grid is represented by first, whose target is position 0. That position is special: it is the causal boundary, so a monotone recency kernel can reach it without addressing an absolute position at all. To check that the absolute side of the duality does not depend on this artefact, we evaluate two interior targets, pos2 and pos5 (attend to absolute position 2, resp. 5), and ran the full study on them: 5 PEs ×\times 2 tasks ×\times 3 depth tiers ×\times 5 seeds ×\times 5 lengths, 750 further trained-model measurements.

The separation is if anything cleaner than at the boundary (Table 6). The absolute encodings solve both interior positions and transfer them perfectly (α60=1.00\alpha_{60}=1.00, LG≥0.97L_G \ge0.97 at L=80L=80), while the relative encodings neither learn nor transfer them. The screen AUC over these ten cells is 1.00, with αL=1.00\alpha_L=1.00 on every generalizing cell and 0.00 on every failing one. The boundary artefact is visible in the comparison: RoPE scores α60=0.20\alpha_{60}=0.20 on first but 0.00 on both interior positions, i.e. the residual score at position 0 came from the causal boundary rather than from any ability to address absolute positions.

PEtaskα60\alpha_{60}train accLGL_G@60LGL_G@80
learned-abspos21.001.001.001.00
learned-abspos51.001.001.001.00
sinusoidalpos21.000.980.980.97
sinusoidalpos51.001.001.000.99
NoPEpos20.000.240.160.16
NoPEpos50.000.220.160.15
ALiBipos20.000.230.160.15
ALiBipos50.000.220.160.15
RoPEpos20.000.310.150.14
RoPEpos50.000.200.160.15

Table 6. Interior fixed-absolute positions (1L1H, mean over 5 seeds). Absolute encodings realize and transfer them; relative encodings do not learn them at all. Compare first, where RoPE scores α60=0.20\alpha_{60}=0.20 purely because position 0 is the causal boundary.

Scale robustness

Because αL\alpha_L depends only on (Φ,tn)(\Phi,t_n), it is identical across model scales; the question is whether the empirical LGL_G it predicts is stable. We re-ran the full study at a 5×5\times larger vocabulary (64 vs 12) and 2×2\times width (d=128d=128 vs 64). The 1L1H cell-level correlation is unchanged (indeed slightly higher): ρ=0.92\rho=0.92 (vs 0.90 at d=64d=64), with sufficient precision 0.94; the scale tier moves 0.36 →\to 0.45 (Table 7). The headline relationship is therefore not an artifact of the tiny vocabulary or width. (This is a robustness check within the synthetic position-driven family, not a claim about natural-language LLMs; see § 7.)

tbl:7: Scale robustness: cell-level Spearman ρ(αL,LG)\rho(\alpha_L, \mathrm{LG}) on learnable cells, at the paper’s default size vs. a larger model. The predictor is identical; only the trained models change. The scale study uses 2 seeds (700 rows), and both columns are computed on the cells the two studies have in common, so the 2L4H entry (0.36) is over 19 cells rather than the 20 of Table 4, where the same quantity over all 20 cells is 0.31.

tiervocab 12, d=64d=64 (main)vocab 64, d=128d=128
1L1H0.900.92
2L4H (scale)0.360.45

Table 7.

Training-length (L0L_0) sensitivity

Is the clean separation an artifact of the default training length L0=20L_0=20? We re-ran the 1-layer 1-head study at L0∈{10,20,40}L_0 \in\{10, 20, 40\}, each evaluated at 3×L03 \times L_0 (so the extrapolation factor is held fixed), 3 seeds. The screen AUC is 1.000 at every L0L_0, and the same four cells generalize in each case (rope prev/skip-3, sinusoidal/learned-abs first); the Theorem 2 verdicts are unchanged (relative bounded offsets transfer; relative growing offsets do not). The separation is therefore not specific to L0=20L_0=20 (Table 8).

Table 8: L0L_0-sensitivity (1L1H, predictor αL\alpha_L / empirical LG at L=3L0L=3L_0). The screen AUC is 1.0 at every training length and the per-cell verdicts are stable; the separation is not an artifact of L0=20L_0=20. Generated by experiments/l0_sensitivity.py.

L0=10  (→30)L_0=10\;(\to30)L0=20  (→60)L_0=20\;(\to60)L0=40  (→120)L_0=40\;(\to120)
screen AUC1.001.001.00
# generalizing cells4/254/254/25
rope / prev (αL\alpha_L / LG)1.00 / 0.931.00 / 0.871.00 / 0.87
rope / skip-31.00 / 1.001.00 / 1.001.00 / 0.98
rope / copy (growing)0.00 / 0.120.00 / 0.100.00 / 0.09
rope / reverse (growing)0.00 / 0.160.03 / 0.140.00 / 0.12
sinusoidal / first (absolute)1.00 / 0.921.00 / 0.831.00 / 0.88
learned-abs / first (absolute)1.00 / 1.001.00 / 1.001.00 / 1.00

Table 8.

A content-aware extension: αL+\alpha_L^+ (with a demonstration)

The binding limitation is (S3): where the content channel carries the target, the positional αL\alpha_L under-predicts. We show the one-sidedness is closable, using a content-driven task, and state what is and is not recovered.

Setup. Augment the realizable space from the positional kernel Kn\mathcal{K}_n to Kn+C\mathcal{K}_n + \mathcal{C}, where C\mathcal{C} is the content-matching channel e(xi)⊤WCe(xj)e(x_i)^\top W_C e(x_j). Define αL+=max⁡(αL,αLcontent)\alpha_L^+ = \max(\alpha_L, \alpha_L^{\mathrm{content}}), where αLcontent=1\alpha_L^{\mathrm{content}}=1 iff the target is realizable by a length-stationary content rule (a token match composed with a fixed shift). The canonical such task is induction: the target at ii is the token following the previous occurrence of xix_i – content-determined, hence αL=0\alpha_L=0 for every PE (no length-dependent positional rule realizes it), while αLcontent=1\alpha_L^{\mathrm{content}}=1.

Demonstration (Table 9). We train induction across PEs. At 1 layer the circuit cannot form (train acc ≈0.25\approx0.25); at 2 layers it is learned (train 0.76–1.0) and generalizes, strongly for ALiBi (LG = 0.84), partially for RoPE/NoPE (0.43/0.34). So positional αL=0\alpha_L=0 mispredicts a cell with LG 0.84 – a real one-sidedness failure – which αL+\alpha_L^+ correctly flags as realizable through the content channel. Caveat: induction LG is PE-modulated (0.26–0.84): the content circuit still needs a working prev-token head, which absolute PEs support poorly, so the binary αLcontent\alpha_L^{\mathrm{content}} over-predicts for sinusoidal/learned-abs. A graded content channel weighting αLcontent\alpha_L^{\mathrm{content}} by the PE’s support for the match circuit – and the multi-head extension that provably escapes Theorem 2 (anchor head + content-match head solves copy at depth 1) – are the natural next steps. The point is narrow: the positional indicator’s blind spot is identifiable, and the content channel recovers a cell it misses.

PEtrain acc (2L4H)LG@60 (2L4H)positional αL\alpha_L
ALiBi0.960.840
RoPE1.000.430
NoPE0.760.340
learned-abs0.990.270
sinusoidal0.980.260

Table 9. Content-driven induction (target = token after the previous occurrence of xix_i): positional αL=0\alpha_L=0 for all PEs, yet 2-layer models generalize (LG up to 0.84). αL+\alpha_L^+ flags the realizable through the content channel regime αL\alpha_L misses; residual PE-modulation of content LG is future work.

A frequency sweep for a discriminating cell. One may reasonably ask for one (PE, task) cell where αL\alpha_L beats the relative/absolute taxonomy. We searched the most promising direction: a frequency-scaled RoPE (still relative) on the content-neutral skip-kk task (the query token is independent of the target s[i−k]s[i-k], so content cannot supply the answer), sweeping the frequency scale to provoke a too smooth to separate nearby offsets failure αL\alpha_L would catch. The result is negative (Table 10): standard and moderately-low frequencies resolve the offset (αL=1\alpha_L=1, LG ≈1\approx1); at scale 0.03 the trained head still generalizes (LG = 0.88) while αL=0\alpha_L=0 – an αL\alpha_L false negative, with the trained model generalizing a target the linear-kernel fit deems unrealizable; and at scale 0.01 the model fails to learn even in-distribution (excluded by the learnability filter). No discriminating cell exists in this family, and the probe instead reveals that αL\alpha_L under-predicts low-frequency relative PEs. Combined with the row-level over-predictions (rope-first), the verdict is that αL\alpha_L matches but does not beat the taxonomy as a predictor; its contribution is the theory that explains the taxonomy, not a superior predictor. (The low-frequency case is not content rescue, since skip-kk is content-neutral; we do not claim to have identified the mechanism behind it.)

Frequency and dimension sensitivity of LL

Since αL\alpha_L is computed from the PE feature map, it is fair to ask whether its verdict is an artifact of our default frequency count, θ\theta-base, or feature dimension. We sweep each (predictor-only, no training; L0=20→L=60L_0=20\to L=60) and find a clean separation: the realizability verdict is stable wherever the theory makes a clean claim, and the only cells whose realizability verdict moves are exactly the sinusoidal bounded-offset cells the theory flags as a selection gap (Prop. 3); a few other cells show small sub-threshold raw movement that never flips the verdict.

Takeaway. Across frequency count, θ\theta-base, and feature dimension, αL\alpha_L’s binary realizability verdict is stable for every regime with a clean theoretical prediction; the residual frequency dependence is confined to the sinusoidal bounded-offset selection gap, which is the behaviour Prop. 3 predicts. The screen is therefore not an artifact of the default PE hyperparameters. (Generated by experiments/freq_dim_sensitivity.py.)

Reproducibility checklist

The full source (predictor, models, tasks, experiments and theory-verification scripts) is released at https://github.com/superajgklasjglaks/positional-realizability.

  • Predictor. αL\alpha_L is in src/spectra.py (simulate(pe,task,L_0,L)); it uses no end-to-end Transformer training, no data samples, and no learned Transformer parameters – only a deterministic kernel-selection on the PE basis. Models: src/model.py (the five PEs); tasks: src/data.py.

  • Seeds. The main study uses seeds {0,1,2,3,4}\{0,1,2,3,4\} (fixed in run_study.py); bootstrap CIs resample cells for the correlations and high-αL\alpha_L rows for the precisions. All randomness is seeded.

  • Configuration. The design grid (PEs ×\times tasks ×\times lengths ×\times seeds ×\times depth tiers) is Table 2; architecture/optimizer/training details are in App. § 11. Tiers and tags are env-overridable in run_study.py (SEEDS, DMODEL, TIERS_ONLY, STUDY_TAG); the run is resumable.

  • Data behind every number. results/study_rows.json (all 2625 rows, including runs the model failed to learn at L0L_0 – no failed runs are silently dropped; the learnability filter train_acc>0.8 is applied explicitly and reported alongside the unconditioned numbers). Summaries in results/study_summary.json.

  • Figures/tables → scripts. Figure 3–Figure 6 and the heatmaps: make_figures.py. Headline statistics (AUC, permutation pp, Spearman + bootstrap CIs, sufficiency precision): review_stats.py. Scale robustness (Table 7): run_study.py with STUDY_TAG=scale. L0-sensitivity (Table 8): l0_sensitivity.py. Frequency/dimension sensitivity (Table 11–Table 12): freq_dim_sensitivity.py. Content extension / induction (Table 9) and the RoPE frequency sweep (Table 10): ablation_fit.py and the content study.

Figure 3. Training-free αL\alpha_L vs. empirical LG across the three tiers (5 seeds). Left (1L1H, the setting the theory describes): learnable cells (blue) give Spearman ρ=0.90\rho=0.90. Center, right (scale, 2L4H, 4L4H): the graded rank correlation weakens (its bootstrap CI includes 0) as the content channel rescues low-αL\alpha_L cells, yet high αL\alpha_L remains a sufficient screen at every depth (precision ≥0.92\ge0.92).

Table 11. αL\alpha_L for RoPE under varying frequency count num (feature dimension m=2m=2 num) and θ\theta-base. The verdict is invariant: fixed relative offsets transfer (prev,skip3=1.00 everywhere), growing offsets never transfer (copy/reverse≈\approx0), and the kernel the L0L_0-fit selects does not hit a fixed absolute position (first stays at chance; a monotone kernel in the family could, but the fit does not select it, see the discussion after Prop. 4). For low-frequency scaling see Table 10.

RoPE settingprevskip3copyreversefirst
num=8 (mm=16)1.001.000.000.000.17
num=16 (mm=32)1.001.000.000.030.20
num=32 (mm=64)1.001.000.000.000.03
base 10310^31.001.000.000.030.05
base 10510^51.001.000.000.030.03

Table 12. αL\alpha_L for sinusoidal under the same sweep. The absolute verdict is invariant (first≈\approx1 everywhere; growing offsets ≈\approx0). The bounded-offset cells (prev/skip3) are the only entries whose verdict moves with frequency – they degrade as frequencies are added (num:8→\to32 drives prev 0.47→\to0.00); the other cells’ raw αL\alpha_L shifts stay sub-threshold (e.g. first 0.93→\to1.00) and never flip the verdict. This is what the theory predicts: enlarging the realizable space does not help the L0L_0-fit select a transferring kernel (existence ≠\ne selection, Prop. 3). Verdict movement appears precisely at the selection gap and nowhere else.

sinusoidal settingprevskip3copyreversefirst
num=8 (mm=16)0.470.500.000.000.93
num=16 (mm=32)0.450.250.070.001.00
num=32 (mm=64)0.000.000.000.001.00
base 10310^30.170.280.000.001.00
base 10510^50.150.120.000.001.00
  • Theory verification. The following claims have executable checks; the list is exhaustive, and claims not named here are supported by their proofs alone: relative growing-offset impossibility (theorem_relative_copy_impossibility.py), the deep-row iff and its counterexample κ=[1.46,1.96,1.80,6.32]\kappa=[1.46, 1.96, 1.80, 6.32] (iff_constant_offset_lg.py), learned-absolute chance 1/(k−1)1/(k-1) (verify_learned_abs_fixed_position_iff.py, theorem2b_learned_abs_montecarlo.py), the absolute/relative duality (duality_abs_vs_rel.py), and the Conjecture 1 cone/selection probes (underdetermined_conj1_*.py).

  • Compute. The full study runs in ≈55\approx55 min on one Apple M3 Pro (MPS); the predictor and all sensitivity sweeps run in seconds on CPU.

References

  1. [1]Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. In Advances in Neural Information Processing Systems (NeurIPS), 2022.arxiv.org/abs/2207.04901
  2. [2]Hanseul Cho, Jaeyoung Cha, Pranjal Awasthi, Srinadh Bhojanapalli, Anupam Gupta, and Chulhee Yun. Position coupling: Improving length generalization of arithmetic transformers using task structure. In Advances in Neural Information Processing Systems (NeurIPS), 2024.arxiv.org/abs/2405.20671
  3. [3]Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. The neural data router: Adaptive control flow in transformers improves systematic generalization. In International Conference on Learning Representations (ICLR), 2022.arxiv.org/abs/2110.07732
  4. [4]Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, et al. A mathematical framework for transformer circuits. Transformer Circuits Thread, 2021. https://transformer-circuits.pub/2021/framework/index.html.
  5. [5]Noah Golowich, Samy Jelassi, David Brandfonbrener, Sham M. Kakade, and Eran Malach. The role of sparsity for length generalization in transformers. arXiv preprint arXiv:2502.16792, 2025.arxiv.org/abs/2502.16792
  6. [6]Zihan Gu, Ruoyu Chen, Han Zhang, Hua Zhang, and Yue Hu. Deconstructing positional information: From attention logits to training biases. arXiv preprint arXiv:2505.13027, 2025.arxiv.org/abs/2505.13027
  7. [7]Suriya Gunasekar, Jason D. Lee, Daniel Soudry, and Nathan Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems (NeurIPS), 2018.arxiv.org/abs/1806.00468
  8. [8]Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics (TACL), 8, 2020.DOI
  9. [9]Xinting Huang, Andy Yang, Satwik Bhattamishra, Yash Sarrof, Andreas Krebs, Hattie Zhou, Preetum Nakkiran, and Michael Hahn. A formal framework for understanding length generalization in transformers. In International Conference on Learning Representations (ICLR), 2025.arxiv.org/abs/2410.02140
  10. [10]Zachary Izzo, Eshaan Nichani, and Jason D. Lee. Quantitative bounds for length generalization in transformers. arXiv preprint arXiv:2510.27015, 2025.arxiv.org/abs/2510.27015
  11. [11]Samy Jelassi, Stéphane d’Ascoli, Carles Domingo-Enrich, Yuhai Wu, Yuanzhi Li, and François Charton. Length generalization in arithmetic transformers. arXiv preprint arXiv:2306.15400, 2023.arxiv.org/abs/2306.15400
  12. [12]Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in transformers. In Advances in Neural Information Processing Systems (NeurIPS), 2023.arxiv.org/abs/2305.19466
  13. [13]William Merrill, Ashish Sabharwal, and Noah A. Smith. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics (TACL), 10, 2022.
  14. [14]Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, et al. In-context learning and induction heads. Transformer Circuits Thread, 2022.arxiv.org/abs/2209.11895
  15. [15]Ofir Press, Noah A. Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference on Learning Representations (ICLR), 2022.arxiv.org/abs/2108.12409
  16. [16]Anian Ruoss, Grégoire Delétang, Tim Genewein, Jordi Grau-Moya, Róbert Csordás, Mehdi Bennani, Shane Legg, and Joel Veness. Randomized positional encodings boost length generalization of transformers. In Annual Meeting of the Association for Computational Linguistics (ACL), 2023.
  17. [17]Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers. In Advances in Neural Information Processing Systems (NeurIPS), 2023.arxiv.org/abs/2306.02896
  18. [18]Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19, 2018.arxiv.org/abs/1710.10345
  19. [19]Jianlin Su, Yu Lu, Shengfeng Pan, Ahmed Murtadha, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 568, 2024.arxiv.org/abs/2104.09864
  20. [21]Davoud Ataee Tarzanagh, Yingcong Li, Xuechen Zhang, and Samet Oymak. Max-margin token selection in attention mechanism. In Advances in Neural Information Processing Systems (NeurIPS), 2023b.arxiv.org/abs/2306.13596
  21. [22]Jie Wang, Tao Ji, Yuanbin Wu, Hang Yan, Tao Gui, Qi Zhang, Xuanjing Huang, and Xiaoling Wang. Length generalization of causal transformers without position encoding. arXiv preprint arXiv:2404.12224, 2024.arxiv.org/abs/2404.12224

Paper details

vlnc:W_jyp7cj29
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents