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 that re-evaluates a selected length--realizing positional kernel on the longer grid, with a scalar read off before any training from alone. Here 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 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 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 : 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 , 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 that re-evaluates the selected length--realizing kernel on the length- grid (§4). It is model-free and data-free, but selection-rule dependent: the value depends on which realizing kernel the -fit selects (§4).

Figure 1. Overview of the method. Select (fit) a single positional head’s kernel at length realizing the task’s target pattern ; transfer the same kernel to a longer grid via (re-evaluate , no retraining); old rows keep their argmax by the causal-mask identity (Thm 1); score the new rows to read off . The whole pipeline uses only , 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 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- 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, 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 . 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.
A realizability framework. We cast LG as kernel transfer: a simulation transfer operator re-evaluates the selected length--realizing kernel at length , and a scalar §4 reads off realizability from alone, using no end-to-end Transformer training, no data samples, and no learned Transformer parameters (only a deterministic kernel-selection).
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- 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 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.
Empirical confirmation and scope. Across 2625 trained-model measurements the theory’s structure holds: 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 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 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 , and ; § 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 ( 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 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. 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 , so it covers this object directly (no min-norm idealization).
Positioning. Table 1 situates 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 is keyed to the PE’s feature map and continuous, computed at the single-attention-head level from . 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 , re-evaluate at ); the new pieces are the closed-form PE-computable witness 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? | granularity | PE-keyed? | direction | |
| RASP-L (Zhou et al., 2024a) | yes | discrete | no | suff. (conj.) |
| C-RASP[Pos] [9] | yes | task, binary | by PE-class | suff. + nec. |
| Izzo et al. [10] | train-length bd. | model-level | no | sufficiency |
| spectral PE [6] | post-hoc | model-level | spectral | – |
| (ours) | yes | cell, cont. | by feat. map | suff. + rel. nec. + conj. |
Table 1. Positioning against the closest LG frameworks. ’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 at position has content embedding ; the PE supplies a positional feature map . We model the query–key logit as separable,
with , learnable. We study position-driven tasks: for each query at length , the head must attend to a task-determined target position (e.g. prev-token ; copy ; reverse; attend-first ). The required pattern is , causal (). Scope hypotheses (S1) single head, one layer, positional-only; (S2) “solve” means correct masked row-argmax with margin ; (S3) content-neutrality on evaluated rows. These are discussed and stress-tested in § 7.
Realizable positional-kernel space. Stacking features (row ), the head’s realizable positional logits form the linear space , of dimension with . NoPE has (constant kernel); learned-absolute has undefined for ; sinusoidal/RoPE/ALiBi are deterministic at all lengths, with RoPE/ALiBi depending only on .
The Simulation Transfer Operator and
A length--trained head is a parameter whose positional kernel realizes the target pattern . Length generalization asks whether the same solves length . We therefore define the simulation transfer operator on the head’s parameter rather than as a map on kernel blocks. A block map would be ill-defined, since a block does not determine when is rank-deficient (then a nullspace direction has but , so two heads with the same kernel transfer differently):
A selection rule picks a realizing from the fit. We use a regularized cross-entropy fit on the kernel coefficients (400 Adam steps, weight decay ), 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 is a different special case. The simulated pattern is , and the simulation alignment is
The scored set is the task’s own query region restricted to the new rows: all of for prev/skip- and the fixed-position tasks, and the part of the second half that lies beyond 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 would score rows on which does not exist and would change the copy/reverse values by a factor that does not vanish with . 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). , and hence , is thus dependent on which realization is selected: different realizing transfer differently, the existence-vs-selection gap we quantify in § 6. The reported uses the regularized cross-entropy section (400 Adam steps, weight decay ); an ablation (App. § 12) shows it tracks LG with versus 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 constraint set. It involves no end-to-end Transformer training, no data samples, and no learned Transformer parameters, only , , and the selection rule. We therefore call 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 induces a family of realizable kernels , and a task demands, at row of length , a target key . Write for the required offset. Then
does contain a kernel whose masked argmax matches 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 transfers, which is what makes meaningful. Theorem 2 answers it for relative families, and the answer has exactly two parts: the demanded offset must settle on a single value on a density-one set of deep rows, and must be attainable as a strict maximizer inside . 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 -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 , and it is the piece we do not have.
Theorem 1 (Simulation sufficiency, for any realizing ). Assume (S1)–(S3). Let be any positional-kernel parameter such that (i) solves length by argmax with margin , and (ii) the alignment computed at , , equals 1 with margin on the new rows . Then solves the task at length with margin .
Proof. New rows are correct with margin by (ii), since are exactly the logits produces at length . For old rows , the causal mask restricts competitors to , so the length- logits there are identical to the length- logits (keys do not exist when ); by (i) those rows are correct with margin . Hence every row is correct.
The proof uses no property of beyond (i)–(ii); in particular it does not require the min-norm interpolant. This matters for the experiments: the reported is computed at the regularized cross-entropy fit , and Theorem 1 applies verbatim to whenever its is 1 – so the theorem certifies the fitted kernel we actually compute. It does not certify the trained transformer, a different object; how often co-occurs with trained-model LG is the empirical question of § 6. Theorem 1 is intentionally elementary: it isolates why the transfer score 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 make the -fit reach (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 , . For every and row , the logit is affine in the key index ; hence the unique masked maximizer is the right endpoint if , the left endpoint if , and a flat tie (margin 0) if . Thus no strict-interior key is ever the unique positive-margin argmax, and any interior-target task (e.g. prev-token, ) is unrealizable at every length for any .
This is not a strawman: canonical ALiBi’s positional basis is exactly affine in the offset, with a sign-constrained slope, so Prop. 1 is why ALiBi-prev has in our experiments (§ 6) – a single ALiBi head cannot place an interior argmax.
Proof. affine in is monotone, so its maximizer is an endpoint, unique unless . An interior target would need and , forcing and simultaneously – a contradiction. The competitor set is at every length, so the conclusion is length-independent.
Proposition 2 (Learned-absolute underdetermination). For learned-absolute PE with fixed for and i.i.d. absolutely-continuous for , and any non-degenerate selection rule depending on trained rows only, the new-row argmax has a law functionally independent of the new-key labels. Write for the off-diagonal new keys and , and assume the row’s target is one of them, , with .
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 is what makes the statement about the untrained coordinates; it holds for the moving targets of prev and skip-k once , which is the case the proposition is used for.
Proof sketch. For new keys depends only on the independent ; the map is a fixed function in which the label never appears, and (trained-rows only) cannot encode it. Conditioned on , the off-diagonal , , are i.i.d. and independent of , so their indices are exchangeable and the argmax is uniform on given that the maximum is attained there, which is (4). We assume as a hypothesis that the maximizer is almost surely unique. This does not follow from , nor from merely being injective on the compared keys: for an antisymmetric with one has identically, so the self-key and the trained key 0 tie for every (App. § 9).
Why both hypotheses are needed. The probability in (4) is conditional because the trained (old) keys and the self-key are not exchangeable with the new keys: the self-key contributes the quadratic , so the global maximum need not lie in at all. Monte-Carlo confirms both parts: at the conditional hit rate is 0.115 against , while the unconditional rate is 0.034 because the winner lands in only 30% of the time; at 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 is equally necessary: if the target is an old key (as in attend-first, where ), the trained keys are precisely the ones the -fit has shaped, and the hit probability can exceed . With a min-norm fitted on the trained rows we measure at up to the bound (feature dimension , ; the ratio grows with and and is below 1 for small ; experiments/verify_prop2_hypothesis.py). That regime is governed by Prop. 4 instead. Finally, a degenerate selection such as makes every logit equal, which is why almost-sure uniqueness needs non-degeneracy. This is underdetermination rather than an empty constraint cone: a rescuing realizing the target on new rows exists with positive probability (–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 a realizing it exists at all lengths (the multi-frequency kernel has a unique global max at , 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 ; empirically the fitted kernel gives 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 , the single component with is increasing for ; at the demanded copy offset is exactly 8833 and this kernel attains . This is far outside the lengths we study (our sinusoidal experiments reach , 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 selection. The transfer operator’s -fit does not recover the fixed-offset rescue: sinusoidal prev decays ( at , 0.34 at ). 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 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 copy/reverse cells of RoPE/ALiBi.
Theorem 2 (Relative-head deep-row characterization). Assume (S1)–(S3). Let denote the scored rows (the task’s query positions in ), so that is the fraction of on which the masked argmax hits the target; we use this one normalization throughout, matching the implementation. Fix a relative (translation-invariant) family of kernels , and consider those that admit a strict unique global maximizer , 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 ; the remaining scored rows form a set of size at most , a bound independent of . Assume the scored set grows, , and write for the kernels in that realize the task at with positive margin, which is the hypothesis Theorem 1 needs in order to turn into length generalization.
Then some with a strict unique global maximizer achieves if and only if there is an offset with
(i) density:
(ii) attainability: for some . (5)
For a given , iff (5)(i) holds with . Both hypotheses are needed. Attainability must be inside rather than : a kernel peaked at the new rows’ offset but failing at has without solving the task at either length, so the existential quantifier alone would not deliver length generalization. And the proof compares against , which is informative only when the scored set grows. The exact conclusion requires more than (5): the realized offset must hit the target on every scored row, including the finitely many rows in , where the causal window clips the argmax below . Consequently fixed-relative-offset tasks (prev, skip-) are realizable by any family containing a kernel whose global maximizer is at , while growing-offset (copy) and within-length-varying (reverse) tasks are not: for every 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 the causal window contains , and maximizes over all offsets , hence over the window; so the masked argmax offset equals the constant , independent of . (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 therefore hits a deep row iff equals that row’s required offset, so
where counts the finitely many clipped rows that happen to be correct. () Given (i), take with . By (6) the deep rows it misses are exactly those with , a vanishing fraction by (i), and since is fixed while . Hence . () Suppose for such a . Put , attainable by construction, giving (ii); by (6) the fraction of scored rows with is , giving (i). For the corollaries, no satisfies (i) when the offset grows (copy, : for every copy row is deep with realized offset , so the missed fraction tends to ) or varies within a length with positive density (reverse: a nested-window monotonicity argument forces failure already at ).
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 length-generalizes the fixed relative offset (prev/skip-: at all lengths). On a fixed absolute position the demand offset grows with the row, so by Theorem 2 no kernel with a strict unique global maximizer attains ; and empirically the kernel the -fit selects decays, at for RoPE on attend-first. (b) Absolute side, for the clamped learned-absolute encoding used in our experiments. Let , so all positions share one feature. Such a head length-generalizes a fixed absolute position in the trained range ( at all lengths, with an -independent margin), and fails on a fixed relative offset: every new key carries the same feature, so the logits over tie exactly and the target cannot be singled out ( with margin ). 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 ( 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 , with a free entry for every pair, is not limited to absolute targets at all: setting 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 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.

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 -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 . That reasoning is wrong, because the causal window truncates at : a monotone increasing , e.g. , puts the masked argmax at 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, 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 -fit does not select the monotone solution, so the transferred accuracy decays with 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 and a quantitative separation holds – for every realizing with old-row margin , the residual forces on some new row – then no single head solves both and .
Remark (why the colspan argument is insufficient). One might conclude impossibility from “”. That does not suffice: the components of acting on the orthogonal complement are unconstrained by the fit and permit a rescuing 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 of full column rank , the map is injective (), so a given kernel block determines and hence . (ii) But this does not decide , because “solving at ” (S2) is an argmax+margin cone of , not a single block: distinct blocks with identical argmax transfer to opposite -verdicts. is decidable only relative to a declared selection rule (e.g. min-norm), not from “the fit” alone – the existence-vs-selection gap again. (iii) The obstruction is not cone-emptiness: an LP witness shows a single solving both and for prev-token sinusoidal in the under-determined regime (rank ), so ; the failure mechanism is selection (Prop. 2) rather than an empty cone. (iv) Sinusoidal escapes the saturation route entirely: at realistic frequency counts is rank-deficient or wildly ill-conditioned (–), so 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: 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: is a property of , and Theorem 1 guarantees that a kernel that realizes the task at with positive margin and reaches with positive margin on the new rows still solves the task at length ; 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 () 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, ) trained at variable length up to and evaluated on extrapolation rows . 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-), 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 ), it is because of a task a model never learned at 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.
| Axis | Levels | Rationale |
| PEs | learned-abs, NoPE, ALiBi, sinusoidal, RoPE | the five canonical PE classes |
| Tasks | prev, skip-2/3/5, copy, reverse, first | fixed-relative, growing-offset, fixed-absolute regimes |
| (+ pos-2/5, App. E) | interior absolute positions, off the causal boundary | |
| Lengths | 30, 40, 50, 60, 80 | extrapolation beyond (1.5×–4×) |
| Seeds | 0, 1, 2, 3, 4 | variance / bootstrap CIs |
| Models | 1L1H, 2L4H, 4L4H | 1-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: separates generalizing from non-generalizing cells. Over all 35 (PE, task) cells (no learnability filter), cell-level separates the 6 that length-generalize (LG ) from the 29 that do not with AUC = 1.00 (base rate 0.17; permutation , 20k shuffles). This is not a fragile 1.0: the margin is wide (min among positives = 1.00 vs. max among negatives = 0.36), and restricting to the 11 non-trivial cells (dropping negatives with ) keeps AUC = 1.0. The screen is thus validated on the hard cells too (all 20 NoPE/ALiBi/copy/reverse cells sit at , 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 (), because the signal is dominantly the clean binary separation; we report it for transparency and turn to the learnable subset for the graded view.
acts primarily as a binary realizability indicator. On the learnable subset (train acc , 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 (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 at 0.5 already gives , and restricting to non-trivial cells () gives . On the only family with genuinely interior values (sinusoidal bounded-offset) there is no positive graded signal: at the cell level ( cells) and at finer aggregations (0.04 row-level, 0.09 at (PE,task, )). We therefore do not claim 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 “ 92%-precision sufficient screen” claim must be qualified. The precision of rises with : 0.925 at , 0.95 at , 0.987 at . At there are 12 violating rows out of 160, and they come from three families: rope-first at (, LG = 0.13, all 5 seeds), sinusoidal-prev at (, LG = 0.14, all 5 seeds), and sinusoidal-first at , , 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 at small 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 (), so PE-awareness is essential. The hand-built taxonomy baseline (relative-PE×bounded V absolute-PE×absolute-task) reaches , within our bootstrap CI: 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 tracking it confirms the theory. The role of 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 can (a low-frequency RoPE, still “relative”): the attempt instead exposed an 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 ) certifies the fitted kernel at which we compute . It does not certify the trained transformer, which is a different parameter. So guarantees the fitted kernel solves length ; whether the trained model does is the empirical question, and the two can diverge: rope-first (, LG 0.13 at ) and sinusoidal-first ( at , LG 0.77 on average and as low as 0.49 on the worst seed) are cases where . We therefore do not claim “the certified object is the validated one.” The right test of the theorem’s relevance is co-occurrence of with trained-model LG, which holds for of high- rows (rising to 98% at ); 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 against (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 and 0.28, with bootstrap CIs that include 0 (Table 4), so beyond depth 1 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 still implies LG (Table 4, Figure 6). The lost graded signal is entirely attributable to low- cells that generalize via mechanisms outside the positional-only abstraction: ALiBi and NoPE realize prev-token and first through the content/recency channel (=0, LG = 1.0; Table 3, bottom), and the set of such cells grows with depth. This is the predicted (S3) boundary: 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.
| PE | task | LG (1L1H) | LG (2L4H) | |
| RoPE | skip5 | 1.00 | 1.00±0.00 | 0.97±0.02 |
| RoPE | prev | 1.00 | 0.87±0.05 | 0.85±0.13 |
| RoPE | copy | 0.00 | 0.10±0.01 | 0.14±0.01 |
| sinusoidal | first | 1.00 | 0.87±0.13 | 0.92±0.04 |
| sinusoidal | skip3 | 0.25 | 0.22±0.03 | 0.11±0.01 |
| learned-abs | first | 1.00 | 1.00±0.00 | 1.00±0.00 |
| learned-abs | prev | 0.00 | 0.08±0.00 | 0.08±0.00 |
| Content-channel cases (S3 violations): under-predicts at scale | ||||
| ALiBi | prev | 0.00 | 0.18±0.00 | 1.00±0.00 |
| ALiBi | first | 0.00 | 0.15±0.01 | 1.00±0.00 |
| NoPE | first | 0.00 | 0.16±0.01 | 1.00±0.00 |
Table 3. Training-free (at ) vs. empirical LG accuracy (mean over 5 seeds), 1-layer 1-head and scale (2L4H) tiers. Top: tracks 1L1H LG. Bottom: at scale, the content/recency channel (outside the positional-only abstraction, S3) lets ALiBi/NoPE generalize where , making the predictor’s one-sidedness visible.
Figure 5. Training-free (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.
| tier | depth | learnable Spearman (95% CI) | sufficiency precision (95% CI) |
| 1L1H | 1 | 0.90 [0.73, 0.95] | 0.925 [0.88, 0.96] |
| 2L4H | 2 | 0.31 [−0.16, 0.76] | 0.94 [0.89, 0.97] |
| 4L4H | 4 | 0.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 (circles) drops with depth (its bootstrap CI includes 0 at depths 2, 4), while sufficiency precision (squares) stays with tight CIs. remains a sufficient screen at all depths.
Figure 4. Empirical LG (solid) and training-free (dashed) vs. test length (train =20), 1L1H. tracks both who generalizes and how LG decays with .
Limitations
App. § 10 sets out, with evidence, the five ways 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 a one-sided screen; the fifth is the one case where high 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, 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 for every PE yet a 2-layer ALiBi model reaches LG 0.84, and a content-aware flags the regime misses (with residual PE-modulation left to future work). (3) The forward question is open. Theorem 1 (stated for any realizing ) certifies that , but it does not say which admit a fitted reaching ; 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 , a sufficiency theorem, and a deep-row characterization for relative heads (for kernels with a strict unique global maximizer, 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 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 under-predicts low-frequency relative PEs. Rather than replacing the received taxonomy, 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 )
Theorem 1 (Simulation sufficiency, any realizing ). Fix any satisfying (i)–(ii). Under (S1)–(S3) the row- logits at any length are for , with the content term argmax-neutral. New rows : by (ii) the simulated has its unique masked maximum at with gap . Old rows : the causal mask restricts the key set to , and for those the features are exactly those present at length ; hence entrywise, so the masked argmax and gap are inherited verbatim from (i). Every row’s unique masked maximizer is with gap .
Remark (why not the min-norm interpolant). Stating this for the min-norm would invoke , which is false unless . The argument needs no such exactness and no choice of : only that the chosen is argmax-correct at and has . Hence it covers the fitted 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 write . Then with , , which is affine in the key index . An affine function on a finite integer chain is monotone, so its maximizers are endpoints, and the maximizer is unique unless (a flat row, margin , excluded by (S2)). For a strict interior target , optimality would require and , i.e. and ; with , this forces and , hence and a zero margin. Therefore no interior key is ever the unique, positive-margin maximizer. Since the competitor set does not depend on , the conclusion holds at every length; prev-token (, interior for ) is thus unrealizable for all .
Caveat. The statement is about the unique positive-margin argmax, not the set inclusion argmax , which fails on the measure-zero locus (there the argmax set is the whole chain).
Proposition 2 (Learned-absolute underdetermination)
Let with fixed and i.i.d. from an absolutely continuous isotropic law, and any rule of the trained rows only (so . Put . Uniqueness: for two keys with the difference is affine in the absolutely continuous , and is nonzero for genuine functional dependence precisely when ; a comparison against the self-key contributes , which is a polynomial of degree two in rather than an affine functional. For pairs of distinct non-self keys the coefficient is nonzero whenever 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 antisymmetric with . Then because is antisymmetric, and because , so the self-key and the trained key carry identical logits for every , while 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 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 is a fixed measurable function of in which the label never appears, and cannot encode it into the new-key geometry; thus does not reference . Chance rate: conditioned on , the off-diagonal new keys are i.i.d. and independent of , so by exchangeability their indices are equally likely to carry the maximum given that the maximum is attained in . With and this gives , and since , the chain rule gives . The old keys and the self-key are not exchangeable with , so they may hold the maximum; that is why the unconditional value is the smaller one. □
Underdetermination, not cone-emptiness. A rescuing realizing the target on all new rows exists with positive probability (Monte Carlo: – of draws; experiments/theorem2b_learned_abs_montecarlo.py); the selection rule is simply blind to the untrained coordinates. The self-key is excluded because is a quadratic (non-exchangeable) form with mean , which is why the conditional rate is rather than .
Proposition 3 (Sinusoidal: existence vs. selection)
(A) Existence. With incommensurate geometric frequencies , the translation-invariant kernel with equality iff for all ; incommensurability forces , so has a unique global maximum at the target offset for any fixed (verified numerically to , far beyond the lowest-frequency period, refuting the intuition that a sinusoidal encoding must fail once the offset exceeds that period). Hence a realizing a fixed offset exists at all lengths. (B) Growing offsets. A translation-invariant kernel with a strict unique global maximizer realizes the constant offset on every deep row (Theorem 2), which can equal only at , and at some where the window clips onto a lower local peak; for every each scored row is missed, so 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. at and ; the correct statement is asymptotic. Without a global maximizer the conclusion fails outright, as the monotone example after the proposition shows.) Existence selection: the -fit does not recover the fixed-offset rescue — under the transfer operator sinusoidal prev decays ( at , at ), and the sub-unit value is quantifying the selection gap. □
Theorem 2 (Relative-head deep-row characterization)
Let on causal keys , with a strict unique global maximizer , under a fixed tie rule. Write for the scored rows (the task’s query positions in ), which is the set averages over. Deep-row constancy (Lemma). For any row the window contains , and no admitted offset beats it because is the maximum over all ; so the masked argmax offset is the constant for all such and all (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, hits a deep scored row if , so with , whose size is at most uniformly in (it is empty once the query region starts above , as happens for copy and reverse),
so the clipped rows contribute . Note that both the theorem and (5) normalize by ; this is the same convention as the implementation, and it matters, since for tasks whose query region is a strict subset of (copy, reverse) the two would differ by a non-vanishing factor.
Assume (5): the required offset equals off a density-zero subset of , and some has . Take that . Old rows are correct because realizes the task at , and the causal-mask identity of Thm 1 preserves that correctness at length ; by (5) the missed deep rows form a vanishing fraction and is fixed, so . (Verified for , up to 5000.) Note both hypotheses are needed: for the canonical ALiBi family , , the maximizer is for every admissible slope, so no ALiBi kernel realizes however constant the demanded offset is.
The exact conclusion needs every scored row, not just the deep ones. The clipped set never leaves , so if a row in it is missed, at every . Example: with leaves the ten rows clipped; a task demanding offset 1 there and 30 on deep rows satisfies exact constancy on all deep rows, yet , i.e. 0.500, 0.875, 0.990, 0.99995 at : it tends to 1 but never equals it. Hence is equivalent to the realized offset hitting the target on every scored row, deep and clipped alike.
Suppose for some . Put , which is attainable in by construction, giving (5)(ii). By (5) the fraction of scored rows with equals , giving (5)(i). For the corollaries, no can satisfy (5)(i) in either of two cases. (a) The offset grows with (copy, ): for all every copy row is deep with realized offset , which cannot equal , so the failing fraction tends to 1 and . (b) It varies within a length (reverse, , distinct offsets ): a nested-window monotonicity argument gives a contradiction already at . Row 18 demands offset 17 and its window is , which contains offset 15, so . Row 17 demands offset 15 and its window contains offset 17, so . The two are incompatible, independent of . A 20k-kernel sweep confirms no solves reverse at (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- “complete iff”. One might hope to add the necessity clause “shallow rows = ”, but it is false: (offsets 0–3, ) makes deep rows take offset 3 but shallow row argmax offset (window values ). Shallow rows are a finite, -dependent set, uncharacterized by a universal formula but immaterial to as —hence the criterion is on deep rows. Two further cautions: the growing-offset clash is asymptotic rather than two-length ( solves copy at both and via shallow clipping); and “bounded offset” is insufficient (the -parity offset 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 . The restriction matters: a kernel peaked at solves copy at , 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 on every deep row would be too strong: only measures a fraction, so a density-zero exceptional set is compatible with . Concretely, let when is a perfect square and 1 otherwise. A kernel peaked at offset 1 fails exactly on the squares, so even though the offset is not eventually constant ( at ). (b) Attainability inside the family. Constancy alone is not sufficient: must be attainable in , and one cannot simply exhibit without checking that it belongs to the PE-induced family. Canonical ALiBi is exactly this case: its family with has its maximizer at offset 0 for every admissible slope, so no ALiBi kernel peaks at 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 grows. Take the unbounded ladder except for ; its values increase without bound, so it has no maximizer at all, and it attains on copy along the whole sequence (we verified this numerically). A kernel that does have a strict unique global maximizer can also solve copy at particular lengths, namely at , where the demanded offset equals , and possibly at some where the causal window clips the argmax onto a lower local peak (for peaked at 100 with a secondary peak at 20 we find at ), but it fails for every , 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 alone. One might also ask for for a support radius , but that would be vacuous for the very families we care about, since RoPE and ALiBi kernels have unbounded support, so and no row would be deep. Globality of the maximizer is what the argument actually needs, and with it the clipped set is . Scope of the characterization. The criterion is on deep rows and the asymptotic ; we do not claim a finite- “complete iff” that also pins shallow rows to – that is false: the kernel (peak at offset 3) makes shallow row select offset 1, not (we reproduce this in App. § 9). Shallow rows are a finite, -dependent set that does not affect the asymptotic . Two further cautions: the growing-offset clash is asymptotic (a kernel peaked at offset 30 solves copy at both and via shallow clipping – there is no two-length contradiction); and “bounded offset” is insufficient. The last point is now exactly condition (5)(i): an -parity offset alternating in is bounded, but each value occurs with density , so no has a vanishing exceptional fraction and 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 . The restriction matters: a kernel peaked at solves copy at , 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 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 : a fixed offset is realized by a whose strict unique global maximizer is , correct on every row at every length (). Attend-first () demands the growing offset , so by Theorem 2 no with a strict unique global maximizer reaches . This is the right qualifier: a monotone increasing kernel such as has no global maximizer and does realize attend-first at every length (the causal window truncates at ), so what defeats attend-first in practice is the sign constraint on the canonical ALiBi slope together with the -fit’s failure to select such a kernel, not translation invariance by itself; the selected RoPE kernel decays as at . Clamped learned-absolute : attend-first is realized by the length-independent column-0-hot kernel (margin at all lengths). A fixed relative offset moves the target across absolute positions into the collapsed range, where all keys share one feature and their logits tie exactly, so 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 and decays with (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 , i.e. object (1) above, which is why it is reported separately from the clamped values.
Failure modes of
Failure modes of . We list the five ways 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.
Selection gap. A rescuing kernel exists, but the -fit does not select it, so despite realizability in principle (sinusoidal fixed-offset: at ; Prop. 3). Existence selection.
Content rescue. The target is carried by the content channel, outside the abstraction, so the positional under-predicts: LG occurs with (induction, and ALiBi/NoPE prev/first at depth; Appendix § 16). This is the binding limitation (S3).
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 can under-predict at scale while remaining a sufficient screen (§ 6).
Low-frequency relative under-prediction. Even within the positional channel and on a content-neutral task, is not a perfect graded predictor: on content-neutral skip- a frequency-scaled (low-frequency) RoPE model generalizes a target the linear-kernel fit deems unrealizable (Table 10, Appendix § 17), so 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 | train acc | LG@60 | |
| 1.0 / 0.3 | 1.00 | 1.00 | 1.00 |
| 0.1 | 1.00 | 0.94 | 0.93 |
| 0.03 | 0.00 | 0.88 | 0.88 |
| 0.01 | 0.00 | 0.23 | 0.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 under-predicts (false negative); at 0.01 the model cannot learn at all.
Overprediction by the fitted kernel. The converse also occurs: the fitted kernel can have high while the trained model selects a different solution and fails to generalize (rope-first at , against LG 0.13; sinusoidal-first at on one seed). Theorem 1 is unaffected, since it is a statement about a single realizing kernel; what fails is the empirical bridge from to the behaviour of .
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 ( LG) intact and are failures of necessity, which is why we call a one-sided screen; (5) is the one case where high 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 does not imply its selection by the -fit. (iii) The learned-absolute rate 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 and not , 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 (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, , GELU MLP (width ), pre-LN, learned token embedding (vocab 12). PEs: NoPE; sinusoidal (additive); learned-absolute (table of size , positions clamped to ); RoPE (rotary on ); ALiBi (fixed geometric slopes). Tiers: 1-layer/1-head, 2-layer/4-head, 4-layer/4-head. Training. AdamW (, wd 0.01), batch 64, 2000 steps, variable train length , , cross-entropy over query positions (ignore-index elsewhere). Tasks (target position , all position-dependent via small vocab): prev (), skip- (, ), copy (), reverse, first (0). Evaluation. Accuracy on extrapolation query rows at , 5 seeds. Predictor fit. Cross-entropy fit of the kernel coefficients to the targets (400 Adam steps), PE-structural constraints imposed (RoPE relative basis; ALiBi recency slope constrained ); strict-unique-argmax scoring on new rows. Compute. Apple M3 Pro (MPS); the full 2625-measurement, 5-seed study runs in 55 min.
Additional results
Table 4 reports the depth trend (H3) over all three tiers; Figure 6 plots it. As depth grows ( 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- rows instead stays high and tight (0.925 0.94 0.97). The lost graded signal is explained by the content channel: the set of low- 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 0.74, RoPE first 0.83 1.00). Depth does not break the sufficient-indicator property; it adds more content-channel routes around a low positional , 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 0.7 | 0.5] with a bootstrap 95% CI over the high- rows. 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 acting as a binary screen rather than a graded predictor once content rescues low- cells.
Inductive-bias ablation (which fit drives the correlation). Table 5 computes three ways on the 75 1L1H (PE,task, ) rows and correlates each with empirical LG. The min-norm interpolant of Theorem 1 yields only ; the regularized cross-entropy fit used throughout yields 0.91, and its weight-decay limit, which approaches the max-margin direction (Soudry et al., [18]), yields 0.92. The predictive content of therefore comes from the cross-entropy direction rather than from the min-norm object, a gap we state here.
| kernel fit | Spearman | Pearson |
| min-norm interpolant (Thm 1’s ) | 0.56 | 0.57 |
| cross-entropy, wd= (reported ) | 0.91 | 0.95 |
| cross-entropy, wd (max-margin) | 0.92 | 0.94 |
Table 5. Inductive-bias ablation (75 rows in the 1L1H setting). The cross-entropy fit, not the min-norm interpolant, drives the – correlation.
Robustness checks. The learnability cutoff is inert: cell-level at train (train accuracy is bimodal). On the 20 dropped cells has std 0.02 (uniformly ), so it provides no rank signal there by construction. Scale robustness (vocab 64, ) is reported in App. § 14; training-length robustness (the screen AUC stays 1.0 and the per-cell verdicts are unchanged at ) in App. § 15; and PE frequency/-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 2 tasks 3 depth tiers 5 seeds 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 (, at ), while the relative encodings neither learn nor transfer them. The screen AUC over these ten cells is 1.00, with on every generalizing cell and 0.00 on every failing one. The boundary artefact is visible in the comparison: RoPE scores 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.
| PE | task | train acc | @60 | @80 | |
| learned-abs | pos2 | 1.00 | 1.00 | 1.00 | 1.00 |
| learned-abs | pos5 | 1.00 | 1.00 | 1.00 | 1.00 |
| sinusoidal | pos2 | 1.00 | 0.98 | 0.98 | 0.97 |
| sinusoidal | pos5 | 1.00 | 1.00 | 1.00 | 0.99 |
| NoPE | pos2 | 0.00 | 0.24 | 0.16 | 0.16 |
| NoPE | pos5 | 0.00 | 0.22 | 0.16 | 0.15 |
| ALiBi | pos2 | 0.00 | 0.23 | 0.16 | 0.15 |
| ALiBi | pos5 | 0.00 | 0.22 | 0.16 | 0.15 |
| RoPE | pos2 | 0.00 | 0.31 | 0.15 | 0.14 |
| RoPE | pos5 | 0.00 | 0.20 | 0.16 | 0.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 purely because position 0 is the causal boundary.
Scale robustness
Because depends only on , it is identical across model scales; the question is whether the empirical it predicts is stable. We re-ran the full study at a larger vocabulary (64 vs 12) and width ( vs 64). The 1L1H cell-level correlation is unchanged (indeed slightly higher): (vs 0.90 at ), with sufficient precision 0.94; the scale tier moves 0.36 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 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.
| tier | vocab 12, (main) | vocab 64, |
| 1L1H | 0.90 | 0.92 |
| 2L4H (scale) | 0.36 | 0.45 |
Table 7.
Training-length () sensitivity
Is the clean separation an artifact of the default training length ? We re-ran the 1-layer 1-head study at , each evaluated at (so the extrapolation factor is held fixed), 3 seeds. The screen AUC is 1.000 at every , 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 (Table 8).
Table 8: -sensitivity (1L1H, predictor / empirical LG at ). The screen AUC is 1.0 at every training length and the per-cell verdicts are stable; the separation is not an artifact of . Generated by experiments/l0_sensitivity.py.
| screen AUC | 1.00 | 1.00 | 1.00 |
| # generalizing cells | 4/25 | 4/25 | 4/25 |
| rope / prev ( / LG) | 1.00 / 0.93 | 1.00 / 0.87 | 1.00 / 0.87 |
| rope / skip-3 | 1.00 / 1.00 | 1.00 / 1.00 | 1.00 / 0.98 |
| rope / copy (growing) | 0.00 / 0.12 | 0.00 / 0.10 | 0.00 / 0.09 |
| rope / reverse (growing) | 0.00 / 0.16 | 0.03 / 0.14 | 0.00 / 0.12 |
| sinusoidal / first (absolute) | 1.00 / 0.92 | 1.00 / 0.83 | 1.00 / 0.88 |
| learned-abs / first (absolute) | 1.00 / 1.00 | 1.00 / 1.00 | 1.00 / 1.00 |
Table 8.
A content-aware extension: (with a demonstration)
The binding limitation is (S3): where the content channel carries the target, the positional 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 to , where is the content-matching channel . Define , where 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 is the token following the previous occurrence of – content-determined, hence for every PE (no length-dependent positional rule realizes it), while .
Demonstration (Table 9). We train induction across PEs. At 1 layer the circuit cannot form (train acc ); 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 mispredicts a cell with LG 0.84 – a real one-sidedness failure – which 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 over-predicts for sinusoidal/learned-abs. A graded content channel weighting 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.
| PE | train acc (2L4H) | LG@60 (2L4H) | positional |
| ALiBi | 0.96 | 0.84 | 0 |
| RoPE | 1.00 | 0.43 | 0 |
| NoPE | 0.76 | 0.34 | 0 |
| learned-abs | 0.99 | 0.27 | 0 |
| sinusoidal | 0.98 | 0.26 | 0 |
Table 9. Content-driven induction (target = token after the previous occurrence of ): positional for all PEs, yet 2-layer models generalize (LG up to 0.84). flags the realizable through the content channel regime 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 beats the relative/absolute taxonomy. We searched the most promising direction: a frequency-scaled RoPE (still relative) on the content-neutral skip- task (the query token is independent of the target , so content cannot supply the answer), sweeping the frequency scale to provoke a too smooth to separate nearby offsets failure would catch. The result is negative (Table 10): standard and moderately-low frequencies resolve the offset (, LG ); at scale 0.03 the trained head still generalizes (LG = 0.88) while – an 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 under-predicts low-frequency relative PEs. Combined with the row-level over-predictions (rope-first), the verdict is that 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- is content-neutral; we do not claim to have identified the mechanism behind it.)
Frequency and dimension sensitivity of
Since is computed from the PE feature map, it is fair to ask whether its verdict is an artifact of our default frequency count, -base, or feature dimension. We sweep each (predictor-only, no training; ) 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, -base, and feature dimension, ’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. 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 (fixed in
run_study.py); bootstrap CIs resample cells for the correlations and high- rows for the precisions. All randomness is seeded.Configuration. The design grid (PEs tasks lengths seeds 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 – no failed runs are silently dropped; the learnability filtertrain_acc>0.8is applied explicitly and reported alongside the unconditioned numbers). Summaries inresults/study_summary.json.
Figures/tables → scripts. Figure 3–Figure 6 and the heatmaps:
make_figures.py. Headline statistics (AUC, permutation , Spearman + bootstrap CIs, sufficiency precision):review_stats.py. Scale robustness (Table 7):run_study.pywithSTUDY_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.pyand the content study.
Figure 3. Training-free vs. empirical LG across the three tiers (5 seeds). Left (1L1H, the setting the theory describes): learnable cells (blue) give Spearman . Center, right (scale, 2L4H, 4L4H): the graded rank correlation weakens (its bootstrap CI includes 0) as the content channel rescues low- cells, yet high remains a sufficient screen at every depth (precision ).
Table 11. for RoPE under varying frequency count num (feature dimension num) and -base. The verdict is invariant: fixed relative offsets transfer (prev,skip3=1.00 everywhere), growing offsets never transfer (copy/reverse0), and the kernel the -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 setting | prev | skip3 | copy | reverse | first |
| num=8 (=16) | 1.00 | 1.00 | 0.00 | 0.00 | 0.17 |
| num=16 (=32) | 1.00 | 1.00 | 0.00 | 0.03 | 0.20 |
| num=32 (=64) | 1.00 | 1.00 | 0.00 | 0.00 | 0.03 |
| base | 1.00 | 1.00 | 0.00 | 0.03 | 0.05 |
| base | 1.00 | 1.00 | 0.00 | 0.03 | 0.03 |
Table 12. for sinusoidal under the same sweep. The absolute verdict is invariant (first1 everywhere; growing offsets 0). The bounded-offset cells (prev/skip3) are the only entries whose verdict moves with frequency – they degrade as frequencies are added (num:832 drives prev 0.470.00); the other cells’ raw shifts stay sub-threshold (e.g. first 0.931.00) and never flip the verdict. This is what the theory predicts: enlarging the realizable space does not help the -fit select a transferring kernel (existence selection, Prop. 3). Verdict movement appears precisely at the selection gap and nowhere else.
| sinusoidal setting | prev | skip3 | copy | reverse | first |
| num=8 (=16) | 0.47 | 0.50 | 0.00 | 0.00 | 0.93 |
| num=16 (=32) | 0.45 | 0.25 | 0.07 | 0.00 | 1.00 |
| num=32 (=64) | 0.00 | 0.00 | 0.00 | 0.00 | 1.00 |
| base | 0.17 | 0.28 | 0.00 | 0.00 | 1.00 |
| base | 0.15 | 0.12 | 0.00 | 0.00 | 1.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 (iff_constant_offset_lg.py), learned-absolute chance (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 min on one Apple M3 Pro (MPS); the predictor and all sensitivity sweeps run in seconds on CPU.
References
- [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]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]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]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]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]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]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]Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics (TACL), 8, 2020.DOI
- [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]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]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]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]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]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]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]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]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]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]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
- [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
- [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



